题解 P3804 【【模板】后缀自动机】
xzyxzy
2018-06-15 12:14:48
[SAM](https://www.cnblogs.com/xzyxzy/p/9186759.html)<身为机房最后一个学SAM的最弱的人折腾了近一周写了一个较为详细的总结>
先把串建好后缀自动机,再拓扑parent树,统计答案
代码中有详细注释,专门给大概了解如何构建SAM但是代码实现有难度的同学食用
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long
using namespace std;
const int N=2010000;
char s[N];
int fa[N],ch[N][26],len[N],siz[N];
int lst=1,node=1,l,t[N],A[N];
ll ans;
void Extend(int c)
{
/*
2+2+2+3行,那么多while但是复杂度是O(n)
*/
int f=lst,p=++node;lst=p;
len[p]=len[f]+1;siz[p]=1;
/*
f为以c结尾的前缀的倒数第二个节点,p为倒数第一个(新建)
len[i] 表示i节点的longest,不用记录shortest(概念在hihocoder后缀自动机1上讲得十分详细)
siz[i]表示以i所代表的endpos的集合元素大小,即所对应的字符串集出现的次数
不用担心复制后的siz,在parent树上复制后的点的siz是它所有儿子siz之和,比1多
*/
while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
/*
把前面的一段没有c儿子的节点的c儿子指向p
Situation 1 如果跳到最前面的根的时候,那么把p的parent树上的父亲置为1
*/
int x=ch[f][c],y=++node;
if(len[f]+1==len[x]) {fa[p]=x;node--;return;}
/*
x表示从p一直跳parent树得到的第一个有c儿子的节点的c儿子
Situation 2 如果节点x表示的endpos所对应的字符串集合只有一个字符串,那么把p的parent树父亲设置为x
Situation 2 和 Situation 3 本质不同!!!与机房dalao们讨论两天才知道Situation 2 必须特判的原因!!!详见上方链接的博客
*/
len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;
memcpy(ch[y],ch[x],sizeof(ch[y]));
while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
/*
Situation 3 否则把x点复制一遍(parent树父亲、儿子),同时len要更新
(注意len[x]!=len[f]+1,因为通过加点会使x父亲改变)
然后把x点和p点的父亲指向复制点y,再将前面所有本连x的点连向y
*/
}
int main()
{
//Part 1 建立后缀自动机
scanf("%s",s); l=strlen(s);
for(int i=l;i>=1;i--) s[i]=s[i-1];s[0]=0;
for(int i=1;i<=l;i++) Extend(s[i]-'a');
//Part 2 按len从大到小排序(和SA好像啊)后计算答案
for(int i=1;i<=node;i++) t[len[i]]++;
for(int i=1;i<=node;i++) t[i]+=t[i-1];
for(int i=1;i<=node;i++) A[t[len[i]]--]=i;
for(int i=node;i>=1;i--)
{//从小到大枚举,实际上在模拟parent树的DFS
int now=A[i];siz[fa[now]]+=siz[now];
if(siz[now]>1) ans=max(ans,1ll*siz[now]*len[now]);
}
printf("%lld\n",ans);
return 0;
}
```