【CodeForces235C】CyclicalQuest【后缀自动机】

1 #include
2 #include
3 #include
4 #include
5
6 using namespace std;
7 const int maxn&＃61;2e6&＃43;10;
8 char s[maxn];
9 struct state{
10 int len,link;
11 int next[26];
12 }st[2*maxn];
13 int last,cur,sz,Q,n;
14 int cnt[2*maxn],c[2*maxn],vis[2*maxn];
15 void init(){
16 sz&＃61;1;
17 last&＃61;cur&＃61;0;
18 st[0].link&＃61;-1;
19 st[0].len&＃61;0;
20 }
21 void build_sam(int c){
22 cur&＃61;sz&＃43;&＃43;;
23 st[cur].len&＃61;st[last].len&＃43;1;
24 cnt[cur]&＃61;1;
25 int p;
26 for(p&＃61;last;p!&＃61;-1&&st[p].next[c]&＃61;&＃61;0;p&＃61;st[p].link){
27 st[p].next[c]&＃61;cur;
28 }
29 if(p&＃61;&＃61;-1)
30 st[cur].link&＃61;0;
31 else{
32 int q&＃61;st[p].next[c];
33 if(st[q].len&＃61;&＃61;st[p].len&＃43;1)
34 st[cur].link&＃61;q;
35 else{
36 int clone&＃61;sz&＃43;&＃43;;
37 st[clone].len&＃61;st[p].len&＃43;1;
38 st[clone].link&＃61;st[q].link;
39 for(int i&＃61;0;i<26;i&＃43;&＃43;)
40 st[clone].next[i]&＃61;st[q].next[i];
41 for(;p!&＃61;-1&&st[p].next[c]&＃61;&＃61;q;p&＃61;st[p].link){
42 st[p].next[c]&＃61;clone;
43 }
44 st[cur].link&＃61;st[q].link&＃61;clone;
45 }
46 }
47 last&＃61;cur;
48 }
49 int cmp(int a,int b){
50 return st[a].len>st[b].len;
51 }
52 int solve(int id){
53 int res&＃61;0;
54 int u&＃61;0,len&＃61;0;
55 for(int i&＃61;0;i<2*n-1;i&＃43;&＃43;){
56 int c&＃61;s[i]-&＃39;a&＃39;;
57 while(u!&＃61;-1&&(st[u].next[c]&＃61;&＃61;0))
58 u&＃61;st[u].link,len&＃61;st[u].len;
59 if(u&＃61;&＃61;-1)
60 u&＃61;0,len&＃61;0;
61 else{
62 u&＃61;st[u].next[c];
63 len&＃43;&＃43;;
64 if(len>&＃61;n&&vis[u]!&＃61;id){
65 res&＃43;&＃61;cnt[u];
66 vis[u]&＃61;id;
67 }
68 while(n!&＃61;1&&st[u].link!&＃61;-1&&st[st[u].link].len>&＃61;n-1)
69 u&＃61;st[u].link,len&＃61;st[u].len;
70 }
71 }
72 return res;
73 }
74
75 int main(){
76 scanf("%s",s);
77 n&＃61;strlen(s);
78 init();
79 for(int i&＃61;0;i)
80 build_sam(s[i]-&＃39;a&＃39;);
81 for(int i&＃61;0;i)
82 c[i]&＃61;i;
83 sort(c,c&＃43;sz,cmp);
84 for(int i&＃61;0;i){
85 int o&＃61;c[i];
86 if(st[o].link!&＃61;-1){
87 cnt[st[o].link]&＃43;&＃61;cnt[o];
88 }
89 }
90
91 scanf("%d",&Q);
92 for(int i&＃61;1;i<&＃61;Q;i&＃43;&＃43;){
93 // memset(vis,0,sizeof(vis));
94 scanf("%s",s);
95 n&＃61;strlen(s);
96 for(int j&＃61;0;j)
97 s[j&＃43;n]&＃61;s[j];
98 int res&＃61;solve(i);
99 printf("%d\n",res);
100 }
101 return 0;
102 }