2019CCPC网络预选赛1003 K-th occurrence 题解_算法日常[18/100]

K-th occurrence

题目链接

VJ上面
HDOJ上面

题解

解法一SAM解法


2019年9月4日19:24:25 补充,不好意思,博主太菜了,补SAM补了6天才看懂,现在第7天才看懂SAM的写法,所以补充一下

  1. 对于题解中说的倍增数组就是代码中的Fa数组,构造极其精巧,建议看一下解法一注释版的代码
  2. 关于权值线段树(就是题解中说的给每种前缀设置一种权值),其实就是建立线段树的时候,让主席树的每个点都有个权值,这样就可以在询问的时候方便的找到第k大了(具体见代码)

解法二SA解法

ST表维护下 后缀排序后的公共长度 的最小值,然后二分找出左右符合的位置,主席树维护下排序后的序列,然后主席树查询第k大即可


2019年8月27日19:23:14 补充(代码也补充为注释版)(发现写blog的时候自己的理解确实有明显加深!所以还是要坚持写blog,推荐大家也可以写点博客啥的)


我们想要找到所有的字串s的第k个,就要找到所有字串出现的位置,用后缀数组去找的方法就是使用后缀的最长公共前缀长度相同来实现寻找,即找到height数组的一段连续区间的最小值都要是s的长度(当然前缀是s),这里可以用二分区间查找st表版本的rmq信息来确定最终的左右区间,然后再用可持久化线段树来找到这个排名区间里的第k个起始位置(之前建立可持久化线段树的时候就通过位置信息让每个rank字串在前一个rank字串所建立的线段树树上(最初为空树)新建一条分支树),rank1字串对应于版本1的主席树(可持久化线段树),rank2字串对应于版本2的主席树,然后我们询问rank区间[l,r]的时候,就是直接用版本[l,r]的主席树的节点数差来看这里面的字串数是否达到了k个(之前已经保证了前缀相同),是则继续访问左子树第k大,否则访问右子树第k-左边的个数大(可以注意到我们左右子树和位置的[l,mid],[mid+1,r]在建树的时候是假定了空间映射关系的!),这样就可以找到对应位置了

AC代码

解法一SAM解法

感谢CSU一个大佬提供代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include<complex>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
char s[100010];
int T[200010][30],fa[200010],len[200010],cnt,last,n;
void build(int v){
int i,p=last,np,q,nq;
last=np=++cnt;
len[np]=len[p]+1;
for(;p&&T[p][v]==0;p=fa[p]) T[p][v]=np;
if(p==0) fa[np]=1;
else{
q=T[p][v];
if(len[q]==len[p]+1) fa[np]=q;
else{
nq=++cnt;
len[nq]=len[p]+1;
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(i=0;i<27;i++) T[nq][i]=T[q][i];
for(;T[p][v]==q;p=fa[p]) T[p][v]=nq;
}
}
}

int root[200010],num;
struct Q{
int L,R,sum;
}A[8000000];

void update(int &x,int l,int r,int k,int v){
A[++num]=A[x];
x=num;
A[x].sum++;
if(l==r) return;
int mid=(l+r)/2;
if(k<=mid) update(A[x].L,l,mid,k,v);
else update(A[x].R,mid+1,r,k,v);
}
int mer(int a,int b,int l,int r){
if(a==0||b==0) return a+b;
int z=++num,mid=(l+r)/2;
if(l==r){
A[z].sum=A[a].sum|A[b].sum;
return z;
}
A[z].L=mer(A[a].L,A[b].L,l,mid);
A[z].R=mer(A[a].R,A[b].R,mid+1,r);
A[z].sum=A[A[z].L].sum+A[A[z].R].sum;
return z;
}
int qkth(int x,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)/2;
if(k<=A[A[x].L].sum) return qkth(A[x].L,l,mid,k);
else return qkth(A[x].R,mid+1,r,k-A[A[x].L].sum);
}

vector<int>g[200010];
int Fa[200010][25],pos[200010];
void dfs(int u){
int i,v;
for(i=1;i<=19;i++) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
for(i=0;i<g[u].size();i++){
v=g[u][i];
Fa[v][0]=u;
dfs(v);
root[u]=mer(root[u],root[v],1,n);
}
}


int main(){
int i,m,t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
cnt=last=1;
memset(T,0,sizeof(T));
for(i=0;i<=200000;i++) g[i].clear();

for(i=1;s[i];i++) build(s[i]-'a');
for(i=1;i<=cnt;i++) g[fa[i]].push_back(i);
int p=1,v;

memset(root,0,sizeof(root));
A[0].L=A[0].R=A[0].sum=num=0;
for(i=1;s[i];i++){
v=s[i]-'a';
p=T[p][v];
pos[i]=p;
update(root[p],1,n,i,1);
}
dfs(1);


int l,r,k,u,a;
while(m--){
scanf("%d%d%d",&l,&r,&a);
p=pos[r];
k=r-l+1;
for(i=19;i>=0;i--) if(len[Fa[p][i]]>=k) p=Fa[p][i];
if(a>A[root[p]].sum) printf("-1\n");
else{
u=qkth(root[p],1,n,a);
printf("%d\n",u-k+1);
}
}
}
return 0;
}

SAM解法注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
/*
2019年9月3日20:44:23 开始看
2019年9月4日11:39:03 再看
主席树+SAM都是刚刚学了一点点皮毛,然后就要接受这种魔鬼题目训练,真是毒打

感觉后缀数组用的是各种后缀的前缀,而后缀自动机则是用前缀的后缀比较多,因为endpos就相当于前缀的感觉
后缀数组的LCP(Longest Common Prefix)问题等价于后缀树的最小公共祖先LCA(Least Common Ancestor)问题
前者是后缀的共同前缀,后者是前缀endpos的共同后缀(link)---> 也即sam构成的后缀link树的lca
有一点点的融会贯通的感觉真他妈的爽啊!

题意:
T组,N次询问, l,r这个子串的第k次出现
*/


#include<iostream>
#include<complex>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
char s[100010];
int T[200010][30],fa[200010],len[200010],cnt,last,n;

/*这里是建立SAM.大佬的板子真滴简洁..*/
void build(int v){
int i,p=last,np,q,nq;
last=np=++cnt;
len[np]=len[p]+1;
for(;p&&T[p][v]==0;p=fa[p]) T[p][v]=np;
if(p==0) fa[np]=1;
else{
q=T[p][v];
if(len[q]==len[p]+1) fa[np]=q;
else{
nq=++cnt;
len[nq]=len[p]+1;
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(i=0;i<27;i++) T[nq][i]=T[q][i];
for(;T[p][v]==q;p=fa[p]) T[p][v]=nq;
}
}
}

/*root[i]数组表示的是endpos为i的节点*/
int root[200010],num;
/*开了40倍的这里是主席树,若只考虑最大的大小和n次修改,每次log(n)的话,那么其实只要2n-1+nlog(n)就行
也就是只要19e5===>也可以直接n << 5 ,即(2^5)*n */
struct Q{
int L,R,sum;
} A[8000000];

/*
pos[i]=p;---> pos数组就是endpos数组,不懂可以参考[oi-wiki/sam](https://oi-wiki.org/string/sam/)
update(root[p],1,n,i,1);
*/
void update(int &x,int l,int r,int k,int v){
/*下面三句话就是1. 获取之前的节点(之前也可能是空节点)信息
2. 让当前的root[]等于新得到的id(sum)_3.然后在这个id上进行玩耍*/
/*总体上就是记录一条新建的边上的所有信息,最主要的是维护权值--为了求出第k大*/
/*我们从递归的角度看进去,发现每个node左右点都是从1开始一直加的,所以这就是权值主席树*/
A[++num]=A[x];
x=num;
A[x].sum++;
if(l==r) return;
int mid=(l+r)/2;
if(k<=mid) update(A[x].L,l,mid,k,v);
else update(A[x].R,mid+1,r,k,v);
}
/*root[u]=mer(root[u],root[v],1,n);*/
int mer(int a,int b,int l,int r){
if(a==0||b==0) return a+b;
int z=++num,mid=(l+r)/2;
if(l==r){
/*因为sum要么一样,要么某一个为0,所以用'或'操作*/
A[z].sum=A[a].sum|A[b].sum;
return z;
}
A[z].L=mer(A[a].L,A[b].L,l,mid);
A[z].R=mer(A[a].R,A[b].R,mid+1,r);
A[z].sum=A[A[z].L].sum+A[A[z].R].sum;
return z;
}
/*
u=qkth(root[p],1,n,a);
printf("%d\n",u-k+1);
返回的是endpos值...也就是返回的是串的右端点...也就是说答案是u-k+1
*/
int qkth(int x,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)/2;
if(k<=A[A[x].L].sum) return qkth(A[x].L,l,mid,k);
else return qkth(A[x].R,mid+1,r,k-A[A[x].L].sum);
}

vector<int>g[200010];
int Fa[200010][25],pos[200010];
/*dfs(1)*/
void dfs(int u){
int i,v;
/*这里i为什么是<=19?...--->每次插入主席树一条边需要log(n),这题就是约等18左右,开到19是为了保险
这里的大的Fa不是sam中的fa*/
/*最最开始这里的初始化都是0,后面就是链状的,用i来dp,真是太巧妙了!
比如Fa[u][0]=0;Fa[v][0]=u;Fa[w][0]=v. 那么Fa[w][1]=Fa[v][0]=u
这就是dp叠层数了===> 所以后面使用的时候就直接用Fa[p][i]就行了*/
for(i=1;i<=19;i++) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
for(i=0;i<g[u].size();i++){
v=g[u][i];
/*v的直接父亲是u...*/
Fa[v][0]=u;
dfs(v);
root[u]=mer(root[u],root[v],1,n);
}
}

int main(){
int i,m,t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
cnt=last=1;
memset(T,0,sizeof(T));
for(i=0;i<=200000;i++) g[i].clear();

/*构建SAM*/
for(i=1;s[i];i++) build(s[i]-'a');
/*i的后缀link放入i,也就是g表示源点到终止节点的方向,fa数组的反hash*/
for(i=1;i<=cnt;i++) g[fa[i]].push_back(i);
int p=1,v;

memset(root,0,sizeof(root));
A[0].L=A[0].R=A[0].sum=num=0;
/*插入构建主席树*/
for(i=1;s[i];i++){
v=s[i]-'a';
/*p就是转移之后的节点啊,所以就是说每个节点在主席树上都是一棵新树*/
p=T[p][v];
/*对,pos就是endpos,转移就是转移到下一个状态*/
pos[i]=p;
update(root[p],1,n,i,1);
}
/*前面生成g[]数组的时候,fa[i]最小值就是1,所以dfs(1)就是从源点跑到各个点去,然后合并每个endpos对应的所有后缀...*/
dfs(1);


int l,r,k,u,a;
while(m--){
scanf("%d%d%d",&l,&r,&a);
/*获取endpos为r的状态点*/
p=pos[r];
/*这里的k竟然是长度...*/
k=r-l+1;
/*为啥又是19,这个是哪来的数字!==>难道说是一个log(n)的大小!好像是!
那么这里的意思应该就是: 找出最短的长度大于要求的字串长的后缀
然后如果对应的节点的权值不够a(其实就是题中说的k),那么直接输出-1
否则就去主席树中找出答案,所以dfs(1)应该就是从源点出发找到终止节点之类的操作


可得好好研究一下Fa数组的作用! 这里从它的作用来看就是用在了自成一体的fa树!就是
答案中说的 扒出 parent树 ,然后利用这个来操作...找到这个串位置对应于主席树的位置
因为之前的fa[]是与主席树没有任何联系的,所以我们需要这个Fa来构建联系
*/
for(i=19;i>=0;i--) if(len[Fa[p][i]]>=k) p=Fa[p][i];
if(a>A[root[p]].sum) printf("-1\n");
else{
u=qkth(root[p],1,n,a);
printf("%d\n",u-k+1);
}
}
}
return 0;
}

解法二SA解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=100100;
int t1[N],t2[N],sum[N],rk[N],ht[N],sa[N],str[N];char s[100100];
/*最小19*N,保守(2^5)*N(即N<<5)*/
struct node1 {
int l, r;
int val;
} tr[N * 22];
int f[N][22];
int root[N], tot;

void get_sa(int n,int m){
int *x=t1,*y=t2;
for(int i=0;i<m;i++) sum[i]=0;
for(int i=0;i<n;i++) sum[x[i]=str[i]]++;
for(int i=1;i<m;i++) sum[i]+=sum[i-1];
for(int i=n-1;i>=0;i--) sa[--sum[x[i]]]=i;
for(int p,j=1;p<=n;j<<=1){
p=0;
for(int i=n-j;i<n;i++) y[p++]=i;
for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(int i=0;i<m;i++) sum[i]=0;
for(int i=0;i<n;i++) sum[x[y[i]]]++;
for(int i=1;i<m;i++) sum[i]+=sum[i-1];
for(int i=n-1;i>=0;i--) sa[--sum[x[y[i]]]]=y[i];
swap(x,y);
p=1;
x[sa[0]]=0;
for(int i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
if(p>=n) break;
m=p;
}
int k=0;n--;
for(int i=0;i<=n;i++) rk[sa[i]]=i;
for(int i=0;i<n;i++){
if(k)k--;else k=0;
int j=sa[rk[i]-1];
while(str[i+k]==str[j+k])k++;
ht[rk[i]]=k;
}
}
/*对ht数组建立st表,这样就能取区间LCP*/
void build(int n) {
for(int i = 1; i <= n; i++) f[i][0] = ht[i];
for(int i = 1; i < 22; i++) {
for(int j = 1; j + (1 << i) - 1 <= n; j++)
f[j][i] = min(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
}
}

int query(int pl, int pr) {
int t = log2(pr - pl + 1.0);
return min(f[pl][t], f[pr - (1 << t) + 1][t]);
}

// root[i] = update1(root[i - 1], 1, n, sa[i] + 1);
/*root数组的key是rk,然后值是key对应的值是线段树节点位置(1是主根)
root也是tr的键,val记录的是某个rk的在root[rk]号树上的**位置前缀和**
然后tr数组就就是记录着主席树上的节点轨迹
*/
int update1(int pre, int l, int r, int pos) {
/*主席树外分支++*/
int cur = ++tot;
/*新开轨迹获取之前轨迹的信息,在之前信息上添加*/
tr[cur] = tr[pre];
tr[cur].val++;
if(l == r) return cur;
int mid = (l + r) >> 1;
/*动态开左孩子或者右孩子点*/
if(pos <= mid) tr[cur].l = update1(tr[pre].l, l, mid, pos);
else tr[cur].r = update1(tr[pre].r, mid + 1, r, pos);
return cur;
}
// queryk(root[cntl - 1], root[cntr], 1, n, k)
/*cntl - 1 的rk也是LCP符合条件的,所以这里需要cntl-1*/
/*pl.pr是rk区间对应的根区间,他们的val值记录着sa之间的差值,类是于线段树rmq=>可以rkq
然后是主席树是同左同右操作的
*/
int queryk(int pl, int pr, int l, int r, int k) {
if(l == r) return l;
int mid = (l + r) >> 1;
if(tr[tr[pr].l].val - tr[tr[pl].l].val >= k) return queryk(tr[pl].l, tr[pr].l, l, mid, k);
else return queryk(tr[pl].r, tr[pr].r, mid + 1, r, k - (tr[tr[pr].l].val - tr[tr[pl].l].val));
}

int main(){
int n, m;int T;
int l, r, k;
int ll, rr, mid;
int tmp;
int cntl, cntr;int cnt;
scanf("%d",&T);
while(T--){
tot = 0;
scanf("%d %d", &n, &m);
scanf("%s",s);
n=strlen(s);
for(int i=0;i<n;i++) str[i] = s[i] - 'a' + 1;
str[n]=0;
get_sa(n+1,30);
/*这里是ht的st_rmq*/
build(n);
for(int i = 1; i <= n ; i++) {
root[i] = update1(root[i - 1], 1, n, sa[i] + 1);
}
while(m--) {
scanf("%d %d %d", &l, &r, &k);
tmp = r - l + 1;
l = rk[l - 1];
ll = 1, rr = l;
while(ll <= rr) {
mid = (ll + rr) >> 1;
cnt = 100000;
if(mid + 1 <= l) cnt = query(mid + 1, l);
if(cnt >= tmp) {
cntl = mid;
rr = mid - 1;
} else {
ll = mid + 1;
}
}
ll = l, rr = n;
while(ll <= rr) {
mid = (ll + rr) >> 1;
cnt = 100000;
if(l + 1 <= mid) cnt = query(l + 1, mid);
if(cnt >= tmp) {
cntr = mid;
ll = mid + 1;
} else {
rr = mid - 1;
}
}
if(cntr - cntl + 1 < k) printf("-1\n");
else {
printf("%d\n", queryk(root[cntl - 1], root[cntr], 1, n, k));
}
}
}
return 0;
}

参考大佬链接

https://blog.csdn.net/mmk27_word/article/details/100045708

每天一句叨叨

世界上总是存在很多的二八定律,不过也应该二八定律,因为总有那么一些人愿意花几倍于人的自律和代价去提高一点点被幸运之神眷顾的机会