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)
累加即可。
/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :3518.cpp
************************************************ */
1//#include <bits/stdc++.h>
2#include <cstring>
3#include <string>
4#include <algorithm>
5#include <iostream>
6#include <cstdio>
7#include <cmath>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#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;
6#define MAXALP 55 //还有大写字母orz
7int k;
8struct state
9{
10 int len, link, nxt[MAXALP];
11};
12const int N =1E5+7;
13state st[N*2];
14int sz, last,rt;
15char s[N];
16int Right[2*N];
17int cnt[2*N],rk[2*N];//for radix sort
18int dp[2*N],lazy[2*N];
19void sa_init()
20{
21 sz = 0;
22 last = rt = ++sz;
23 st[1].len = 0;
24 st[1].link=-1;
25 ms(st[1].nxt,-1);
26}
27void sa_extend(int c)
28{
29 int cur = ++sz;
30 st[cur].len = st[last].len + 1;
31 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
32 int p;
33 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
34 st[p].nxt[c] = cur;
35 if (p == -1) {
36 st[cur].link = rt;
37 } else {
38 int q = st[p].nxt[c];
39 if (st[p].len + 1 == st[q].len) {
40 st[cur].link = q;
41 } else {
42 int clone = ++sz ;
43 st[clone].len = st[p].len + 1;
44 st[clone].link = st[q].link;
45 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
46 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
47 st[p].nxt[c] = clone;
48 st[q].link = st[cur].link = clone;
49 }
50 }
51 last = cur;
52}
53void topo()
54{
55 ms(cnt,0);
56 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
57 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
58 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
59}
60char ST[N];
61int idx( char c)
62{
63 if (c>='a'&&c<='z') return c-'a';
64 return c-'A'+26;
65}
66int main()
67{
68#ifndef ONLINE_JUDGE
69 freopen("./in.txt","r",stdin);
70#endif
71 ms(Right,0);
72 ms(lazy,0); //parent树上的lazy标记，最后子底向上更新
73 scanf("%s",ST);
74// cout<<"ST:"<<ST<<endl;
75 sa_init();
76 for (int i = 0,len = strlen(ST); i < len ; i++)
77 {
78 Right[sz+1] = 1;
79 sa_extend(idx(ST[i]));
80 }
81 topo();
82 for ( int i = sz ; i >=1 ; i--) if (st[rk[i]].link!=-1)Right[st[rk[i]].link]+=Right[rk[i]];
1 LL ans = 0 ;
2 for ( int i = sz ; i >= 1 ; i--)
3 {
4 int v = rk[i];
5 ans = ans + 1LL*Right[v]*(Right[v]+1)/2*(st[v].len-st[st[v].link].len);
6 printf("ans:%lld\n",ans);
7 }
8 printf("%lld\n",ans);
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}
/* ***********************************************
Author :111qqz
Created Time :2017年11月15日 星期三 19时06分15秒
File Name :SAM.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson 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=5E5+7;
7struct SAM
8{
9 #define MAXALP 30
10 struct state
11 {
12 int len, link, nxt[MAXALP];
13 int leftmost; //某个状态的right集合中r值最小的
14 int rightmost;//某个状态的right集合的r的最大值
15 int Right; //right集合大小
16 };
17 state st[N*2];
18 char S[N];
19 int sz, last,rt;
20 char s[N];
21 int cnt[2*N],rk[2*N];//for radix sort
22 int idx(char c)
23 {
24 if (c>='a'&&c<='z') return c-'a';
25 return c-'A'+26;
26 }
27 void init()
28 {
29 sz = 0;
30 ms(st,0);
31 last = rt = ++sz;
32 st[1].len = 0;
33 st[1].link=-1;
34 st[1].rightmost=0;
35 ms(st[1].nxt,-1);
36 }
37 void extend(int c,int head)
38 {
39 int cur = ++sz;
40 st[cur].len = st[last].len + 1;
41 st[cur].leftmost = st[cur].rightmost = head;
42 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
43 int p;
44 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
45 st[p].nxt[c] = cur;
46 if (p == -1) {
47 st[cur].link = rt;
48 } else {
49 int q = st[p].nxt[c];
50 if (st[p].len + 1 == st[q].len) {
1 st[cur].link = q;
2 } else {
3 int clone = ++sz ;
4 st[clone].len = st[p].len + 1;
5 st[clone].link = st[q].link;
6 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
7 st[clone].leftmost = st[q].leftmost;
8 st[clone].rightmost = st[q].rightmost;
9 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
10 st[p].nxt[c] = clone;
11 st[q].link = st[cur].link = clone;
12 }
13 }
14 last = cur;
15 }
16 void build ()
17 {
18 init();
19 for ( int i = 0,_len = strlen(S) ; i < _len ; i++)
20 {
21 st[sz+1].Right = 1;
22 extend(idx(S[i]),i);
23 }
24 }
25 void topo()
26 {
27 ms(cnt,0);
28 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
29 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
30 //rk[1]是len最小的状态的标号
31 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
32 }
33 void pre() //跑拓扑序，预处理一些东西
34 {
35 for ( int i = sz ; i >= 2 ; i--)
36 {
37 int v = rk[i];
38 int fa = st[v].link;
39 if (fa==-1) continue;
40 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
41 st[fa].Right += st[v].Right;
42 }
43 }
44 void solve()
45 {
1 LL ans = 0 ;
2 for ( int i = sz ; i >= 2 ; i--)
3 {
4 int v = rk[i];
5 if (st[v].link==-1) continue;
6 ans = ans + 1LL * st[v].Right*(st[v].Right+1)/2 * (st[v].len-st[st[v].link].len);
7 }
8 printf("%lld\n",ans);
9 }
10 int LCS(char *s)
11 {
12 int ans = 0,len = 0 ;
13 int p = rt;
14 for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
15 {
16 int ID = s[i]-'a';
17 if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
18 else
19 {
20 while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
21 if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
22 }
23 // printf("len:%d\n",len);
24 ans = max(ans,len);
25 }
26 return ans;
27 }
28}A;
29char B[N];
30int main()
31{
32#ifndef ONLINE_JUDGE
33 freopen("./in.txt","r",stdin);
34#endif
35 scanf("%s",A.S);
36 A.build();
37 A.topo();
38 A.pre();
39 A.solve();
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}