hdu 3518 Boring counting (后缀自动机)
http://acm.hdu.edu.cn/showproblem.php?pid=3518
题意：
给一个字符串，问字符串中，至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。
思路：
考虑SAM
SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。
考虑其right集合，如果right集合中最大的r设为rightmost,最小的r设为leftmost.
那么如果rightmost-leftmost+1 > st[i].len ，说明什么呢？
说明该状态所表示的最长的字符串能够至少放下两个而不重叠。
即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。
如果最长的能放下，那么其他的也一定能放下。因此对答案贡献为st[i].len - st[st[i].link].len
如果rightmost-leftmost+1<=st[i].len，也就是rightmost-leftmost<st[i].len
这个时候长的字符串因为重叠了不能出现2次，但是短的字符串仍然可以贡献答案。
考虑如下图：
此时对答案的贡献为rightmost-leftmost+1 - (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len
综合2种情况，SAM中每个节点对答案的贡献是** min(rightmost-leftmost,st[i].len)-st[st[i].link].len**
需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案
leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。
/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :4436.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;
6#define MAXALP 30
7const int mod = 2012;
8struct state
9{
10 int len, link, nxt[MAXALP];
11 int leftmost; //由于要求出现位置最小的，所以维护某个状态的right集合中r值最小的
12 int rightmost;
13};
14const int N =1E3+7;
15state st[N*2];
16int sz, last,rt;
17char s[N];
18int cnt[2*N],rk[2*N];//for radix sort
19void sa_init()
20{
21 sz = 0;
22 last = rt = ++sz;
23 st[1].len = 0;
24 st[1].link=-1;
25 st[1].rightmost=0;
26 ms(st[1].nxt,-1);
27}
28void sa_extend(int c,int head)
29{
30 int cur = ++sz;
31 st[cur].len = st[last].len + 1;
32 st[cur].leftmost = st[cur].rightmost = head;
33 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
1 int p;
2 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
3 st[p].nxt[c] = cur;
4 if (p == -1) {
5 st[cur].link = rt;
6 } else {
7 int q = st[p].nxt[c];
8 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}
16void topo()
17{
18 ms(cnt,0);
19 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
20 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
21 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
22}
23char S[N];
24int main()
25{
26#ifndef ONLINE_JUDGE
27 freopen("./in.txt","r",stdin);
28#endif
1 while (~scanf("%s",S))
2 {
3 if (S[0]=='#') break;
4 sa_init();
5 for ( int i = 0,len = strlen(S) ; i < len ; i++)
6 {
7 sa_extend(S[i]-'a',i);
8 }
1 topo();
2 for ( int i = sz ; i >=1 ; i--)
3 {
4 int v = rk[i];
5 int fa = st[v].link;
6 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
7// printf("len:%d rightmost %d leftmost:%d\n",st[i].len,st[i].rightmost,st[i].leftmost);
8 }
1 LL ans = 0 ;
2 for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
3 ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
4 printf("%lld\n",ans);
5 }
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;
6#define MAXALP 30
7const int N=1E3+7;
8struct SAM
9{
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 void init()
23 {
24 sz = 0;
25 last = rt = ++sz;
26 st[1].len = 0;
27 st[1].link=-1;
28 st[1].rightmost=0;
29 ms(st[1].nxt,-1);
30 }
31 void extend(int c,int head)
32 {
33 int cur = ++sz;
34 st[cur].len = st[last].len + 1;
35 st[cur].leftmost = st[cur].rightmost = head;
36 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
37 int p;
38 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
39 st[p].nxt[c] = cur;
40 if (p == -1) {
41 st[cur].link = rt;
42 } else {
43 int q = st[p].nxt[c];
44 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 topo()
17 {
18 ms(cnt,0);
19 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
20 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
21 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
22 }
23 void pre() //跑拓扑序，预处理一些东西
24 {
25 for ( int i = sz ; i >= 2 ; i--)
26 {
27 int v = rk[i];
28 int fa = st[v].link;
29 if (fa==-1) continue;
30 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
31 st[fa].Right += st[v].Right;
32 }
33 }
34 void solve()
35 {
1 LL ans = 0 ;
2 for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
3 ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
4 printf("%lld\n",ans);
5 }
6}A;
7int main()
8{
9#ifndef ONLINE_JUDGE
10 freopen("./in.txt","r",stdin);
11#endif
1 while (~scanf("%s",A.S))
2 {
3 if (A.S[0]=='#') break;
4 A.init();
5 for ( int i = 0,len = strlen(A.S) ; i < len ; i++)
6 {
7 A.extend(A.S[i]-'a',i);
8 }
9 A.topo();
10 A.pre();
11 A.solve();
12 }
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}