codeforces 123D. String(后缀自动机)
题目链接：http://codeforces.com/problemset/problem/123/D
题意：
如果字符串y在字符串x中出现n次，那么F(x,y)=n*(n+1)/2
现在给一个字符串，求所有的F(s,x)的和，x为字符串的所有不相同的子串．
思路：
这道题可以考虑用后缀数组做，麻烦一点：codeforces-123D-解题报告(SA)
直接SAM
right[v]就是SAM上状态表示的所有字符串出现的次数。
那么每个状态的答案就是right[v](right[v]+1)/2(st[v].len-st[st[v].link].len)
累加即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月08日 星期三 18时50分18秒
4File Name :3518.cpp
5************************************************ */
6
7//#include <bits/stdc++.h>
8#include <cstring>
9#include <string>
10#include <algorithm>
11#include <iostream>
12#include <cstdio>
13#include <cmath>
14#define PB push_back
15#define fst first
16#define sec second
17#define lson l,m,rt<<1
18#define rson m+1,r,rt<<1|1
19#define ms(a,x) memset(a,x,sizeof(a))
20typedef long long LL;
21#define pi pair < int ,int >
22#define MP make_pair
23
24using namespace std;
25const double eps = 1E-8;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28const int inf = 0x3f3f3f3f;
29#define MAXALP 55 //还有大写字母orz
30int k;
31struct state
32{
33 int len, link, nxt[MAXALP];
34};
35const int N =1E5+7;
36state st[N*2];
37int sz, last,rt;
38char s[N];
39int Right[2*N];
40int cnt[2*N],rk[2*N];//for radix sort
41int dp[2*N],lazy[2*N];
42void sa_init()
43{
44 sz = 0;
45 last = rt = ++sz;
46 st[1].len = 0;
47 st[1].link=-1;
48 ms(st[1].nxt,-1);
49}
50void sa_extend(int c)
51{
52 int cur = ++sz;
53 st[cur].len = st[last].len + 1;
54 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
55 int p;
56 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
57 st[p].nxt[c] = cur;
58 if (p == -1) {
59 st[cur].link = rt;
60 } else {
61 int q = st[p].nxt[c];
62 if (st[p].len + 1 == st[q].len) {
63 st[cur].link = q;
64 } else {
65 int clone = ++sz ;
66 st[clone].len = st[p].len + 1;
67 st[clone].link = st[q].link;
68 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
69 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
70 st[p].nxt[c] = clone;
71 st[q].link = st[cur].link = clone;
72 }
73 }
74 last = cur;
75}
76void topo()
77{
78 ms(cnt,0);
79 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
80 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
81 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
82}
83char ST[N];
84int idx( char c)
85{
86 if (c>='a'&&c<='z') return c-'a';
87 return c-'A'+26;
88}
89int main()
90{
91#ifndef ONLINE_JUDGE
92 freopen("./in.txt","r",stdin);
93#endif
94 ms(Right,0);
95 ms(lazy,0); //parent树上的lazy标记，最后子底向上更新
96 scanf("%s",ST);
97// cout<<"ST:"<<ST<<endl;
98 sa_init();
99 for (int i = 0,len = strlen(ST); i < len ; i++)
100 {
101 Right[sz+1] = 1;
102 sa_extend(idx(ST[i]));
103 }
104 topo();
105 for ( int i = sz ; i >=1 ; i--) if (st[rk[i]].link!=-1)Right[st[rk[i]].link]+=Right[rk[i]];
106
107 LL ans = 0 ;
108 for ( int i = sz ; i >= 1 ; i--)
109 {
110 int v = rk[i];
111 ans = ans + 1LL*Right[v]*(Right[v]+1)/2*(st[v].len-st[st[v].link].len);
112 printf("ans:%lld\n",ans);
113 }
114 printf("%lld\n",ans);
115
116#ifndef ONLINE_JUDGE
117 fclose(stdin);
118#endif
119 return 0;
120}
121
122
123
124
125
126
127
128
129
130/* ***********************************************
131Author :111qqz
132Created Time :2017年11月15日 星期三 19时06分15秒
133File Name :SAM.cpp
134************************************************ */
135
136#include <bits/stdc++.h>
137#define PB push_back
138#define fst first
139#define sec second
140#define lson l,m,rt<<1
141#define rson m+1,r,rt<<1|1
142#define ms(a,x) memset(a,x,sizeof(a))
143typedef long long LL;
144#define pi pair < int ,int >
145#define MP make_pair
146
147using namespace std;
148const double eps = 1E-8;
149const int dx4[4]={1,0,0,-1};
150const int dy4[4]={0,-1,1,0};
151const int inf = 0x3f3f3f3f;
152const int N=5E5+7;
153struct SAM
154{
155 #define MAXALP 30
156 struct state
157 {
158 int len, link, nxt[MAXALP];
159 int leftmost; //某个状态的right集合中r值最小的
160 int rightmost;//某个状态的right集合的r的最大值
161 int Right; //right集合大小
162 };
163 state st[N*2];
164 char S[N];
165 int sz, last,rt;
166 char s[N];
167 int cnt[2*N],rk[2*N];//for radix sort
168 int idx(char c)
169 {
170 if (c>='a'&&c<='z') return c-'a';
171 return c-'A'+26;
172 }
173 void init()
174 {
175 sz = 0;
176 ms(st,0);
177 last = rt = ++sz;
178 st[1].len = 0;
179 st[1].link=-1;
180 st[1].rightmost=0;
181 ms(st[1].nxt,-1);
182 }
183 void extend(int c,int head)
184 {
185 int cur = ++sz;
186 st[cur].len = st[last].len + 1;
187 st[cur].leftmost = st[cur].rightmost = head;
188 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
189 int p;
190 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
191 st[p].nxt[c] = cur;
192 if (p == -1) {
193 st[cur].link = rt;
194 } else {
195 int q = st[p].nxt[c];
196 if (st[p].len + 1 == st[q].len) {
197
198 st[cur].link = q;
199 } else {
200 int clone = ++sz ;
201 st[clone].len = st[p].len + 1;
202 st[clone].link = st[q].link;
203 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
204 st[clone].leftmost = st[q].leftmost;
205 st[clone].rightmost = st[q].rightmost;
206 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
207 st[p].nxt[c] = clone;
208 st[q].link = st[cur].link = clone;
209 }
210 }
211 last = cur;
212 }
213 void build ()
214 {
215 init();
216 for ( int i = 0,_len = strlen(S) ; i < _len ; i++)
217 {
218 st[sz+1].Right = 1;
219 extend(idx(S[i]),i);
220 }
221 }
222 void topo()
223 {
224 ms(cnt,0);
225 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
226 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
227 //rk[1]是len最小的状态的标号
228 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
229 }
230 void pre() //跑拓扑序，预处理一些东西
231 {
232 for ( int i = sz ; i >= 2 ; i--)
233 {
234 int v = rk[i];
235 int fa = st[v].link;
236 if (fa==-1) continue;
237 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
238 st[fa].Right += st[v].Right;
239 }
240 }
241 void solve()
242 {
243
244 LL ans = 0 ;
245 for ( int i = sz ; i >= 2 ; i--)
246 {
247 int v = rk[i];
248 if (st[v].link==-1) continue;
249 ans = ans + 1LL * st[v].Right*(st[v].Right+1)/2 * (st[v].len-st[st[v].link].len);
250 }
251 printf("%lld\n",ans);
252 }
253 int LCS(char *s)
254 {
255 int ans = 0,len = 0 ;
256 int p = rt;
257 for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
258 {
259 int ID = s[i]-'a';
260 if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
261 else
262 {
263 while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
264 if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
265 }
266 // printf("len:%d\n",len);
267 ans = max(ans,len);
268 }
269 return ans;
270 }
271}A;
272char B[N];
273int main()
274{
275#ifndef ONLINE_JUDGE
276 freopen("./in.txt","r",stdin);
277#endif
278 scanf("%s",A.S);
279 A.build();
280 A.topo();
281 A.pre();
282 A.solve();
283
284#ifndef ONLINE_JUDGE
285 fclose(stdin);
286#endif
287 return 0;
288}