【模板】后缀自动机 (SAM)
首先我们知道 SAM 是个自动机，字符串 $s$ 的 SAM 满足如下几个条件：
有一个初始状态 $t_0$。
从 $t_0$ 开始到某个终止状态结束的路径可以表示字符串 $s$ 的一个后缀。
SAM 包含 $s$ 的所有后缀信息。
满足包含所有后缀信息的状态下具有最少的状态数（即最小性）。
首先我们引入字符串 $s$ 的子串 $t$ 的 $endpos(t)$，其中 $endpos(t)$ 是一个集合，它表示所有 $t$ 出现的结束位置。
然后我们可以发现，对于某些字符串，比如 $t_1$ 和 $t_2$，$endpos(t_1)$ 和 $endpos(t_2)$ 有可能是相同的。我们把 $t_1$ 和 $t_2$ 归于一个等价类。
然后我们发现一个等价类显然可以对应上一个 SAM 中的状态，对于某个状态，它是可以属于多个后缀的（到达终止状态的路径），这几个后缀有着共同的前缀，显然这个子串又有一堆后缀，一部分后缀与其属于一个等价类，一部分后缀不属于。
显然对于一个状态的这一部分后缀，若属于同一个等价类，它们的长度显然是连续的。
算了先滚去背代码再说吧。。。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#define ll int
using namespace std;
const ll N=1e6;
struct State{ll len,link,d;ll nxt[27];}st[N*2+5];
ll n,sz,last,ans,tot;
ll ver[N*2+5],nxt[N*2+5],head[N*2+5];
char s[N+5];
inline void SAM_Init() {sz=1;st[sz].len=0;st[sz].link=0;last=sz;}
inline void SAM_Extend(ll c) {
ll cur=++sz,p=last;st[cur].len=st[last].len+1;st[sz].d=1;
for(;p&&!st[p].nxt[c];p=st[p].link) st[p].nxt[c]=cur;
if(!p) {st[cur].link=1;}
else {
ll q=st[p].nxt[c];
if(st[p].len+1==st[q].len) {st[cur].link=q;}
else {
ll clone=++sz;
st[clone]=st[q];
st[clone].len=st[p].len+1;st[clone].d=0;
st[q].link=st[cur].link=clone;
for(;p&&st[p].nxt[c]==q;p=st[p].link) st[p].nxt[c]=clone;
}
}
last=cur;
}
inline void Addedge(ll u,ll v) {
ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}
inline void DP(ll p) {
for(ll i=head[p];i;i=nxt[i]) {
DP(ver[i]);st[p].d+=st[ver[i]].d;
}
if(st[p].d>1) {ans=max(ans,st[p].d*st[p].len);}
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
int main() {
SAM_Init();scanf("%s",s);n=strlen(s);
for(ll i=0;i<n;i++) {SAM_Extend(s[i]-'a');}
for(ll i=2;i<=sz;i++) {Addedge(st[i].link,i);}
DP(1);
write(ans);
return 0;
}
|