hdu 4622 Reincarnation(后缀自动机)

题意：

给你一个串，然后有q个询问，每次询问区间有多少个不同的子串。

题解：

后缀自动机n^2预处理，O(1)回答。

对于每插入一个字符，该字符串新增加的不同的子串的个数为ml[p]-ml[pre[p]]。ml为最大步长

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 #define mst(a,b) memset(a,b,sizeof(a))
 4 using namespace std;
 5 
 6 int ans;
 7 const int N=1e5+7,tyn=26,M=N*2;
 8 struct SAM{//字符长度,字符集大小,根结点为1,ACADD
 9     int pre[M],son[M][tyn],ml[M],tot,last,p,x,r,q;
10     inline int gid(char x){return x-'a';}
11     inline void nc(int s,int &p){
12         ml[p=++tot]=s,pre[tot]=0,mst(son[tot],0);
13     }
14     void clear(){tot=0,nc(0,last);}
15     void add(int w){
16         nc(ml[x=last]+1,p),last=p;
17         while(x&&!son[x][w])son[x][w]=p,x=pre[x];
18         if(!x)pre[p]=1;
19         else if(ml[x]+1==ml[q=son[x][w]])pre[p]=q;
20         else{
21             nc(ml[x]+1,r),pre[r]=pre[q],pre[p]=pre[q]=r;
22             memcpy(son[r],son[q],sizeof(son[r]));
23             while(x&&son[x][w]==q)son[x][w]=r,x=pre[x];
24         }
25         ans+=ml[p]-ml[pre[p]];
26     }//从1开始
27     void build(char *s){for(int i=1;s[i];++i)add(gid(s[i]));}
28 }sam;
29 
30 char s[N];
31 int t,q,n,ret[2007][2007];
32 
33 int main()
34 {
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%s",s+1);
39         n=strlen(s+1);
40         F(i,1,n)
41         {
42             sam.clear(),ans=0;
43             F(j,i,n)
44             {
45                 sam.add(sam.gid(s[j]));
46                 ret[i][j]=ans;
47             }
48         }
49         scanf("%d",&q);
50         while(q--)
51         {
52             int l,r;
53             scanf("%d%d",&l,&r);
54             printf("%d
",ret[l][r]);
55         }
56     }
57     return 0;
58 }

View Code