struct SAM {
static const int MAXN = 1e6 + 10;
int nxt[2 * MAXN][26];
int len[2 * MAXN];
int lnk[2 * MAXN];
int cnt[2 * MAXN];
int siz;
int lst;
void Init() {
siz = 1;
lst = 1;
ms(nxt[1]);
len[1] = 0;
lnk[1] = 0;
cnt[1] = 0;
}
void Extend(int c) {
int u = ++siz, p = lst;
lst = u;
len[u] = len[p] + 1;
cnt[u] = 1;
while(p != 0 && nxt[p][c] == 0) {
nxt[p][c] = u;
p = lnk[p];
}
if(p == 0) {
lnk[u] = 1;
return;
}
int q = nxt[p][c];
if(len[p] + 1 == len[q]) {
lnk[u] = q;
return;
}
int v = ++siz;
mc(nxt[v], nxt[q]);
len[v] = len[p] + 1;
lnk[v] = lnk[q];
cnt[v] = 0;
while(p != 0 && nxt[p][c] == q) {
nxt[p][c] = v;
p = lnk[p];
}
lnk[q] = v;
lnk[u] = v;
}
int c[2 * MAXN];
int a[2 * MAXN];
void Calc() {
ll ans = 0;
for(int i = 1; i <= siz; ++i)
c[i] = 0;
for(int i = 1; i <= siz; ++i)
++c[len[i]];
for(int i = 1; i <= siz; ++i)
c[i] += c[i - 1];
for(int i = 1; i <= siz; ++i)
a[c[len[i]]--] = i;
for(int i = siz; i >= 1; --i) {
int u = a[i];
cnt[lnk[u]] += cnt[u];
ll tmp = 1LL * cnt[u] * len[u];
if(cnt[u] > 1)
cmax(ans, tmp);
}
printf("%lld
", ans);
}
} sam;
有唯一的一个初始状态，有一个或多个终止状态。
从初始状态开始的任意一条由nxt组成的路径，都是原串的一个子串；原串的每一个子串都对应一条这样的路径。
由初始状态开始的到终止状态的任意一条由nxt组成的路径，都是原串的一个后缀；原串的每一个后缀都对应这样的一条路径。
也就是子串对应（从初始状态开始的）路径，状态对应终止于这个状态的路径的集合。
endpos(t)字符串s的子串t在s的后缀自动机上对应的所有终止位置（状态）的集合。
两个非空子串(u,v)，设|u|<=|v|，假如拥有相同的endpos，当且仅当u是v的后缀，且每一次出现u都是以v的后缀形式存在的。
两个非空子串，要么endpos毫不相交，要么其中一个的endpos是另一个的子集（在这种情况下，大的endpos集合对应的子串是小的endpos集合对应的子串的后缀）。
每个endpos集合对应一类子串。
后缀连接lnk组成一棵树，满足endpos(v)是endpos(lnk(v))的子集。
本质不同的子串的数量：
每个状态对应的（本质不同的）子串数量是 len(v)，每次去掉前面的一个字符让len-1就得到了一个新的串。注意这个状态的净贡献是len[u]-len[lnk[u]] ，也就是减去被lnk父亲贡献过的部分。
也可以不使用lnk，使用nxt进行动态规划，使用nxt时，后缀自动机是一个DAG，直接写一个记忆化搜索完事。
dp[u]表示从状态u开始的路径的数量。
(dp[u]=1+sum dp[v])
本质不同的字符的总长度：
每个状态对应的（本质不同的）子串的总长度是 (len(v)+(len(v)+1))/2。也是要注意减去lnk父亲贡献过的部分。
也可以不使用lnk，使用nxt进行动态规划，使用nxt时，后缀自动机是一个DAG，直接写一个记忆化搜索完事。
dp1[u]表示从状态u开始的路径的数量，dp2[u]表示从状态u开始的路径的总长度，注意第二个转移表示这里面每一个串的长度加起来是dp2[v]，其中每一个都变长了1，增加了dp1[v]。
(dp1[u]=1+sum dp1[v])
(dp2[u]=sum (dp2[v]+dp2[v]))
最小循环移位：
字符串S+S包含S的所有循环移位作为子串，对S+S构造后缀自动机，从初始状态开始贪心选最小的字符进行转移，然后转移恰好|S|次就行。
某个子串的出现次数：
找到这个子串对应的endpos集合，输出这个集合的大小。endpos集合不能显式维护，所以只能找这个集合的大小。假如一个节点不是复制创建的（也就是被插入创建的），则它的endpos大小为1，复制的状态和初始状态的endpos为0。然后cnt(lnk(v))+=cnt(v)把更长位置的出现次数叠加到短的状态上。（上述代码就是这个模板）
所有子串的出现次数：
在上面的“某个子串的出现次数”问题里面，一个状态实际上对应着 len[u]-len[lnk[u]] 个子串，这些子串拥有相同的贡献，他们的贡献都是 cnt[u] 。
字典序第k大的子串：
由于“子串对应从初始状态开始的路径”，那么实际上要找字典序第k大的路径。用动态规划求出从每个状态开始有多少种路径。
假如是求本质不同的，则使用
dp[u]表示从状态u开始的路径的数量。
(dp[u]=1+sum dp[v])
假如不是求本质不同的，则每一种节点开始并结束有cnt[u]种，也就是
(dp[u]=cnt[u]+(sum dp[v]))
bool vis[2 * MAXN];
ll dp[2 * MAXN];
ll DP(int u) {
if(vis[u])
return dp[u];
dp[u] = cnt[u];
for(int i = 0; i < 26; ++i) {
int v = nxt[u][i];
if(v != 0)
dp[u] += DP(v);
}
vis[u] = 1;
return dp[u];
}
void Show(int u) {
vector<pair<char, int> > res;
for(int i = 0; i < 26; ++i) {
int v = nxt[u][i];
if(v != 0)
res.eb('a' + i, v);
}
// printf("u=%d
", u);
// printf(" lnk=%d
", lnk[u]);
// printf(" cnt=%d
", cnt[u]);
// printf(" dp=%lld
", dp[u]);
// for(auto v : res)
// printf(" v=%c %d
", v.first, v.second);
for(auto v : res)
Show(v.second);
return;
}
void Calc2(int k) {
for(int i = 1; i <= siz; ++i)
vis[i] = 0;
DP(1);
int u = 1;
while(k > 0) {
for(int i = 0; i < 26; ++i) {
int v = nxt[u][i];
if(v != 0) {
if(k > dp[v])
k -= dp[v];
else {
putchar('a' + i);
k -= cnt[v];
u = v;
break;
}
}
}
}
putchar('
');
}