传送门：http://hihocoder.com/problemset/problem/1445
【题解】
大概看了一天的后缀自动机，总算懂了一些
这篇文章写的非常好，诚意安利：Suffix Automaton Tutorial - Hunt Zhan
我就是看了这个大概懂了。
整个过程大概是：每次插入一个state可能会分裂原有的state的transition，就维护这个transition即可。
要用par[x]记录suffix-link是谁。
过程中可以不用记录minlen，因为$minlen[i] = maxlen[par[i]] + 1$，这点非常重要。
这题前面写了后缀自动机，然后上面像统计子树一样统计，后来发现，复杂度是$O(n * 26)$，似乎太大了，TLE了。
其实后缀自动机的每个state都含有若干子串，所有state的含有子串个数之和就是总个数了。
每个state含有子串个数为$maxlen[i] - minlen[i]$，这里把$minlen[i]$替换成$maxlen[par[i]] + 1$即可，不需要再求$minlen[i]$。
这样复杂度就差不多$O(n)$了，常数小了。
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h> using namespace std; typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e6 + , M = 2e6 + ;
const int mod = 1e9+; char str[N];
struct SAM {
int ch[M][], par[M], ml[M];
int siz, rt, last;
inline void set() {
siz = rt = last = ;
memset(ch, , sizeof ch);
memset(par, , sizeof par);
memset(ml, , sizeof ml);
}
inline void extend(int c) {
int p = last, cur = ++siz;
ml[cur] = ml[p] + ;
for (; p && !ch[p][c]; p = par[p]) ch[p][c] = cur;
if(!p) par[cur] = rt;
else {
int q = ch[p][c];
if(ml[q] == ml[p] + ) par[cur] = q;
else {
int sq = ++siz;
par[sq] = par[q];
for (int i=; i<; ++i) ch[sq][i] = ch[q][i];
ml[sq] = ml[p] + ;
par[q] = par[cur] = sq;
for (; p && ch[p][c] == q; p = par[p]) ch[p][c] = sq;
}
}
last = cur;
}
}S; /*
ll f[M];
inline void dfs(int x) {
f[x] = 1;
for (int i=0; i<26; ++i) {
if(!S.ch[x][i]) continue;
dfs(S.ch[x][i]);
f[x] += f[S.ch[x][i]];
}
}
*/ int main() {
scanf("%s", str+); S.set();
for (int i=; str[i]; ++i) S.extend(str[i] - 'a');
ll ans = ;
for (int i=; i<=S.siz; ++i) {
if(i == S.rt) continue;
ans += S.ml[i] - S.ml[S.par[i]];
}
cout << ans;
return ;
}