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
11
12using namespace std;
13const double eps = 1E-8;
14const int dx4[4]={1,0,0,-1};
15const int dy4[4]={0,-1,1,0};
16const int inf = 0x3f3f3f3f;
17const int N=2017;
18const int maxn = 4017;
19LL ret;
20struct node{
21 node*nxt[26],*fail;
22 LL len,cnt;
23 void init()
24 {
25 for ( int i = 0 ; i < 26 ; i++) nxt[i]=NULL;
26 fail=NULL;
27 len=cnt=0;
28 }
29};
30struct SAM{
31 node no[maxn];
32 node*root;
33 int cnt;
34 node* newnode(){
35 ms(no[cnt].nxt,0);
36 no[cnt].fail=NULL;
37 no[cnt].len=no[cnt].cnt=0;
38 return &no[cnt++];
39 }
40 SAM(){
41 cnt = 0;
42 root = newnode();
43 }
44 void init()
45 {
46 cnt = 0;
47 root =newnode();
48 no[0].init();
49 }
50 node*add(int c,node*p){
51 node*cur = newnode();
52 cur->len = p->len+1;
53 node *lst = cur;
54 while(p&&!p->nxt[c]){
55 p->nxt[c] = cur;
56 p = p->fail;
57 }
58 if(!p){
59 cur->fail = root;
60 return cur;
61 }
62 node *q = p->nxt[c];
63 if(p->len+1==q->len){
64 cur->fail = q;
65 }else{
66 node*nq = newnode();
67 *nq = *q;
68 q->fail = cur->fail = nq;
69 nq->len = p->len+1;
70 while(p&&p->nxt[c]==q){
71 p->nxt[c] = nq;
72 p = p->fail;
73 }
74 }
75 return cur;
76 }
77 LL calc(node *cur)
78 {
79 return cur->len - cur->fail->len;
80 }
81};
82SAM sam;
83string A;
84LL ans[N][N];
85int main()
86{
87 #ifndef ONLINE_JUDGE
88 freopen("./in.txt","r",stdin);
89 #endif
90 int T;
91 cin>>T;
92 while (T--)
93 {
94 cin>>A;
95 int q;
96 ms(ans,0);
97 int len = A.length();
98 //预处理一下，就只需要2000个SAM了
99 for ( int i = 0 ; i < len ; i++)
100 {
101 sam.init();
102 node *cur = sam.root;
103 for ( int j = i ; j < len ; j++)
104 {
105 cur = sam.add(A[j]-'a',cur);
106 ans[i+1][j+1] = ans[i+1][j] + sam.calc(cur);
107
108 }
109 }
110 scanf("%d",&q);
111 while (q--)
112 {
113 int l,r;
114 scanf("%d %d",&l,&r);
115 printf("%lld\n",ans[l][r]);
116 }
117 }
118
119 #ifndef ONLINE_JUDGE
120 fclose(stdin);
121 #endif
122 return 0;
123}