spoj nsubstr Substrings (后缀自动机 模板题)
http://www.spoj.com/problems/NSUBSTR/en/
题意：
f[i]指长度为i的串出现次数的最大值。这里的不同出现指，可以有重复串，只要起始位置不同就视为不同的出现。
求f[1]..f[lenth]。
思路：
我们知道，SAM上的节点是right集合的等价类。
一个子串的right集合是指在一个母串中，某个子串所有出现位置的右端点的集合。
如果两个子串的right集合完全相同，那么就可以归结为同一个节点，也就是说这两个子串对于SAM是等价的。
因为在SAM上，这两个子串后，添加若干字符得到的后缀都是一样的。
所以一个SAM节点的个数，就是right集合等价类的个数（如果不考虑初始状态）
对于SAM某一个节点，其能表示的子串有一个范围，设为[MIN,MAX]
SAM的一个节点能表示的子串的含义是说，这些子串的right集合相同。
而一个子串出现的次数就是其right集合的大小。
考虑SAM上的某个节点，其表示的长度区间在[MIN,MAX]的子串都出现了|right|次
如果我们直接从MIN更新到MAX有点太暴力了，实际上这里我们可以只更新f[MAX]
由于长度i-1的子串出现的次数一定大于等于长度为i的子串出现的次数，所以最后长度从大到小更新f即可。
现在的问题就变成了如何求right集合。
实际上我们不需要知道right集合的具体组成，只需要知道right集合的大小。
考虑一棵parent树，树上某个节点的right集合就是该节点的所有儿子节点的right集合的并集
因此我们只需要在parent上自低向上更新right集合的大小就可以了。
如何保证在parent树上是自底向上更新呢？
我们只需要按照len,也就是SAM中所有节点能表示的子串的MAX值从大到小的顺序更新right集合。
原因是parent树上，儿子的len一定比父亲的len长。
注意到，对于parent树上的叶子节点，其right集合是1，这也是我们的初始状态。
部分实现细节见代码注释。
关于SAM的详细学习笔记日后补
20171109Update:
注释写错了一处，a[1]应该是len最短的状态的标号，之前写成了最长的。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月08日 星期三 18时50分18秒
4File Name :nsubstr.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
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
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23#define MAXALP 26
24
25struct state
26{
27 int len, link, nxt[MAXALP];
28};
29const int N =3E5+7;
30state st[N*2];
31int Right[2*N]; //right[i]表示第i个状态的right集合大小
32int sz, last,rt;
33char s[N];
34int cnt[2*N],a[2*N];//for radix sort
35void sa_init()
36{
37 sz = 0;
38 last = rt = ++sz;
39 st[1].len = 0;
40 st[1].link=-1;
41 ms(st[1].nxt,-1);
42 ms(cnt,0);
43}
44void sa_extend(int c)
45{
46 int cur = ++sz;
47 st[cur].len = st[last].len + 1;
48 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
49 int p;
50 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
51 st[p].nxt[c] = cur;
52 if (p == -1) {
53 st[cur].link = rt;
54 } else {
55 int q = st[p].nxt[c];
56 if (st[p].len + 1 == st[q].len) {
57 st[cur].link = q;
58 } else {
59 int clone = ++sz ;
60 st[clone].len = st[p].len + 1;
61 st[clone].link = st[q].link;
62 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
63 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
64 st[p].nxt[c] = clone;
65 st[q].link = st[cur].link = clone;
66 }
67 }
68 last = cur;
69}
70int f[N]; //答案
71int main()
72{
73 #ifndef ONLINE_JUDGE
74// freopen("./in.txt","r",stdin);
75 #endif
76 sa_init();
77 ms(f,0);
78 ms(Right,0);
79 scanf("%s",s+1);
80 int len = strlen(s+1);
81 for ( int i = 1 ; i <= len ; i++)
82 {
83 Right[sz+1] = 1; //初始化right集合的大小
84 sa_extend(s[i]-'a');
85 }
86 // a simple radix sort
87 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
88 for ( int i = 1 ; i <= len ; i++) cnt[i]+=cnt[i-1];
89 for (int i = 1 ; i <= sz ;i++) a[cnt[st[i].len]--] = i;
90 //将len按照从大到小的顺序存入临时数组a，a[1]表示len最*短*的状态的标号。
91
92 for ( int i = sz ; i >= 1 ; i--) Right[st[a[i]].link]+=Right[a[i]];
93 //按照len从大到小的顺序更新right集合。
94 //考虑一棵parent树，某个状态的right集合就是其就是其所有儿子节点的并集。
95 //我们对parent树自底向上更新，由于儿子的len一定比父亲的len长，所以自底向上更新也就是按照len从大到小更新
96 //
97 //
98 for ( int i = rt ; i <= sz ; i++) f[st[i].len] = max(f[st[i].len],Right[i]) ;
99 //长度为st[i].len的字符串出现了right[i]次
100
101 for ( int i = len ; i >= 1 ; i--) f[i] = max(f[i],f[i+1]);
102 //由于我们之前对于一个状态，只是更新了其表示的子串中长度最长的那个(也就是st[i].len)
103 //但实际上每个状态表示的子串的长度是在区间[st[st[i].link]+1,st[i].len]
104 //这个状态表示的每一个长度在该区间中的子串实际上都出现了right[i]次
105 //我们只更新了最大，所以最后要倒序更新一下。
106 //这样做的正确性在于，长度i-1的子串出现的次数一定大于等于长度为i的子串出现的次数。
107 for ( int i = 1 ; i <= len ; i++) printf("%d\n",f[i]);
108
109
110 #ifndef ONLINE_JUDGE
111 fclose(stdin);
112 #endif
113 return 0;
114}