【CF#235C】Cyclical Quest

  • 后缀自动机重修系列第三题

题目大意:是给定一个字符串S,再给Q个询问,每次询问字符串Xi的循环同构在S中出现的次数和

首先把模板串建成SAM,那么对于每一个串,把它扩成两倍,然后在SAM上匹配,注意每次计算贡献时要沿parent树找到mx[x]>=l的最小的x,因为如果parent(x)可以匹配,那么parent(x)的贡献一定大于x

然后就是注意xi中可能出现重复子串,怎么处理呢?

我们知道SAM上的一个子串在SAM上对应唯一的一个节点,那么为了防止重复子串的影响,只需要计算过答案后标记一下该节点即可。

注意用memset会TLE,我们需要一些奇淫技巧,具体看代码

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2000010
using namespace std;
int n,m,cnt(1),last(1),mx[MAXN],par[MAXN],c[MAXN],vis[MAXN],id[MAXN],Right[MAXN],tr[MAXN][27];
char ch[MAXN];
void extend(int x){
int np=++cnt,p=last; Right[np]=1;
mx[np]=mx[p]+1; last=np;
while(p&&!tr[p][x]) tr[p][x]=np,p=par[p];
if(!p) par[np]=1;
else{
int q=tr[p][x];
if(mx[q]==mx[p]+1) par[np]=q;
else{
int nq=++cnt; mx[nq]=mx[p]+1;
memcpy(tr[nq],tr[q],sizeof(tr[q]));
par[nq]=par[q]; par[q]=par[np]=nq;
while(p&&tr[p][x]==q) tr[p][x]=nq,p=par[p];
}
}
}
void topsort(){
for(int i=1;i<=cnt;++i) c[mx[i]]++;
for(int i=1;i<=n;++i) c[i]+=c[i-1];
for(int i=1;i<=cnt;++i) id[c[mx[i]]--]=i;
for(int i=cnt;i;--i) Right[par[id[i]]]+=Right[id[i]];
}
void solve(int k){
int now=1,len=0,ans=0;
for(int i=1;i<=n*2;++i){
while(now&&!tr[now][ch[i]-'a']) now=par[now],len=mx[now];
if(!now) len=0,now=1;
else now=tr[now][ch[i]-'a'],len++;
while(now&&mx[par[now]]>=n) now=par[now],len=mx[now];
if(vis[now]!=k&&len>=n) ans+=Right[now],vis[now]=k;
}
printf("%d\n",ans);
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%s",ch+1); n=strlen(ch+1);
for(int i=1;i<=n;++i) extend(ch[i]-'a');
topsort();
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%s",ch+1); n=strlen(ch+1);
for(int j=1;j<=n;++j) ch[n+j]=ch[j];
solve(i);
}
return 0;
}
文章目录
,