\(Sam\) 复杂度和空间都成线性，但不能只开 \(n\)
\(endpos\)
1，定义 \(endpos\) 为每个子串出现的开头集合
2，定义 \(Sam\) 每个节点为“状态”，则每个状态对应着一个或者多个 \(endpos\) 相同的集合
后缀链接\(link\)
1，连向当前子串后缀中非同一 \(endpos\) 的最大那个
code：洛谷P3804后缀自动机
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6+17;
int i, j, n, m, k, top = 1, u = 1;
char s[N];
vector<int> v[N];
long long ans;
struct pt {
int len, f, cnt, nx[26];
#define f(p) d[p].f//后缀链接link
#define len(p) d[p].len//同一 endpos下的最大字符串长度
#define cnt(p) d[p].cnt//该字符串（或者endpos集合大小）出现次数
int& operator [] (const int&x) {return nx[x-'a'];}
} d[N];//源点是1
void ins(int x) {
int p = u, q, t, i;
u = ++top;//新建节点
len(u) = len(p)+1;//长度为上次原串被包含的节点，即终止链的末尾
cnt(u) = 1;//标记出现次数
for(; p&&!d[p][x]; p=f(p)) d[p][x] = u;//顺着终止链找到原来的所有后缀,然后连一条当前字符的边到u,这样方能加入新的后缀
if(p) {
q = d[p][x];
if(len(p)+1 == len(q)) f(u) = q;//q里面没有比新后缀更长的串
else {//分裂q，一部分包含比新后缀更长的串，一部分（t）包含新后缀本身及比新后缀短的串
d[t=++top] = d[q], len(t) = len(p)+1, cnt(t) = 0;
for(; p&&d[p][x]==q; p=f(p)) d[p][x] = t;//把新后缀及新后缀的后缀从q中剔除
f(u) = f(q) = t;
}
} else f(u) = 1;//如果p的link都可以直接连向x，那么u直接连向空集
}
void dfs(int x) {
for(int y: v[x]) {
dfs(y);
cnt(x) += cnt(y);
}
if(cnt(x) > 1)
ans = max(ans, 1ll*cnt(x)*len(x));
}
signed main() {
scanf("%s", s+1);
for(i=1; s[i]; i++) ins(s[i]);
for(i=2; i<=top; i++) v[f(i)].push_back(i);
dfs(1), printf("%lld", ans);
return 0;
}