hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)
http://acm.hdu.edu.cn/showproblem.php?pid=4622
题意：
给一个字符串，给出若干询问，每组询问给一个区间[l,r]，问区间中本质不同的字符串的个数。
思路：
观察发现，有10000组查询，字符串的长度最多才2000，所以可以预处理一波。
我们先考虑如何处理整个区间中，本质不同的子串数量。
考虑SAM，由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串，同时后缀自动机是最简的，所以问题也就变成了从初始状态开始不同路径的数量。
每个节点 u 表示的子串长度在 [min[u],max[u]]范围内.
又由于max(u.fail) = min(u)-1
因此u表示的子串的长度就是变成了**(max[u.fail],max[u] ] (注意区间，是左闭右开)**
由于每个长度的串都出现了一次，因此这个状态子串的个数就是max[u] - max[u.fail]
如果是统计整个串的本质不同的串的个数，那么buildSAM之后统计一下就行了。
现在是询问区间。
问题变成了，从[l,r]到[l,r+1]，答案的改变是什么。
在SAM上添加一个字符之后，SAM当前的状态变成了cur,那么实际上，对答案的贡献，就是初始状态到新的状态cur的不同路径数目。
也就是max[cur]-max[cur.fail]
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lnxt l,m,rt<<1
6#define rnxt m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2017;
7const int maxn = 4017;
8LL ret;
9struct node{
10 node*nxt[26],*fail;
11 LL len,cnt;
12 void init()
13 {
14 for ( int i = 0 ; i < 26 ; i++) nxt[i]=NULL;
15 fail=NULL;
16 len=cnt=0;
17 }
18};
19struct SAM{
20 node no[maxn];
21 node*root;
22 int cnt;
23 node* newnode(){
24 ms(no[cnt].nxt,0);
25 no[cnt].fail=NULL;
26 no[cnt].len=no[cnt].cnt=0;
27 return &no[cnt++];
28 }
29 SAM(){
30 cnt = 0;
31 root = newnode();
32 }
33 void init()
34 {
35 cnt = 0;
36 root =newnode();
37 no[0].init();
38 }
39 node*add(int c,node*p){
40 node*cur = newnode();
41 cur->len = p->len+1;
42 node *lst = cur;
43 while(p&&!p->nxt[c]){
44 p->nxt[c] = cur;
45 p = p->fail;
46 }
47 if(!p){
48 cur->fail = root;
49 return cur;
50 }
51 node *q = p->nxt[c];
52 if(p->len+1==q->len){
53 cur->fail = q;
54 }else{
55 node*nq = newnode();
56 *nq = *q;
57 q->fail = cur->fail = nq;
58 nq->len = p->len+1;
59 while(p&&p->nxt[c]==q){
60 p->nxt[c] = nq;
61 p = p->fail;
62 }
63 }
64 return cur;
65 }
66 LL calc(node *cur)
67 {
68 return cur->len - cur->fail->len;
69 }
70};
71SAM sam;
72string A;
73LL ans[N][N];
74int main()
75{
76 #ifndef ONLINE_JUDGE
77 freopen("./in.txt","r",stdin);
78 #endif
79 int T;
80 cin>>T;
81 while (T--)
82 {
83 cin>>A;
84 int q;
85 ms(ans,0);
86 int len = A.length();
87 //预处理一下，就只需要2000个SAM了
88 for ( int i = 0 ; i < len ; i++)
89 {
90 sam.init();
91 node *cur = sam.root;
92 for ( int j = i ; j < len ; j++)
93 {
94 cur = sam.add(A[j]-'a',cur);
95 ans[i+1][j+1] = ans[i+1][j] + sam.calc(cur);
1 }
2 }
3 scanf("%d",&q);
4 while (q--)
5 {
6 int l,r;
7 scanf("%d %d",&l,&r);
8 printf("%lld\n",ans[l][r]);
9 }
10 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}