后缀自动机
P3804 【模板】后缀自动机（SAM）
可解决的问题：
-
在另一个字符串中搜索一个字符串的所有出现位置；
-
计算给定的字符串中有多少个不同的子串．
算法步骤：
先假设我们建好了这个结构，考虑添加一个字符 \(c\)。
考虑三种情况：
情况一：原字符串 \(s\) 的后缀路径上，没有经由 \(c\) 的转移，直接连一条 \(c\) 边。
情况二：原字符串 \(s\) 的后缀路径上已经有了 \(c\) 边但只连了一个 \(c\) 边，直接把 \(cur\) 的 \(link\) 指向该点。
情况三：原字符串 \(s\) 的后缀路径上已经有了 \(c\) 边但还有其他边，新建一个点 \(clone\) 克隆该点，并把 \(len\) 改为仅从 \(p\) 经 \(c\) 这一个字符转移过来，即 \(sam[clone].len=sam[p].len+1\)。并把在 \(p\) 链上通过 \(c\) 指向 \(q\) 的所有节点都指向 \(clone\)。最后修改当前节点和 \(q\) 点的 \(link\)。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;
struct node{int len,link;//分别记录endpos集合相同的子串最长长度和前向边指向的节点（后缀链接）map<int,int> ch;//记录转移点
}sam[N];
int idx,last;
ll val[N],ans;//dfs后的val[i]表示有多少个子串在i处结尾
vector<int> q[N];
void insert(int c){int cur=++idx;//新节点 sam[cur].len=sam[last].len+1;//长度等于上一个+1val[cur]=1;int p=last;while(p!=-1&&sam[p].ch.count(c)==0){//先连没有c这条边的sam[p].ch[c]=cur;p=sam[p].link;}if(p==-1) sam[cur].link=0;//找到头了else{int q=sam[p].ch[c];//q是已经连了c这条边的集合if(sam[q].len==sam[p].len+1) sam[cur].link=q;//如果长度说明只连了一个 c 就直接把新节点的前向边连过来 else{//否则说明p还连了其他边 int clone=++idx;sam[clone]=sam[q];//克隆q节点 sam[clone].len=sam[p].len+1;//改变它的len为只连c的len sam[cur].link=sam[q].link=clone;//因为clone的len比q的小,所以clone是q的前缀,因此cur和q的link都是clone while(p!=-1&&sam[p].ch[c]==q){//现在q就要作为一个不在这条链上的节点了，把这条链上原本走c连到q的点全部连到clone，这样q就可以彻底脱离这条链了 sam[p].ch[c]=clone;p=sam[p].link;}} }last=cur;//更新last
}
void dfs(int x){//计算以x为结尾的字串的总数 for(int i=0;i<q[x].size();i++){int y=q[x][i];dfs(y);val[x]+=val[y];}
}
int main(){string s;cin>>s;sam[0].link=-1;//重要！！！方便判断是否走到头，不加会死循环 for(int i=0;i<s.size();i++) insert(s[i]-'a');for(int i=1;i<=idx;i++) q[sam[i].link].push_back(i);//通过前向边 link 建图 dfs(0);for(int i=1;i<=idx;i++) if(val[i]>1) ans=max(ans,val[i]*sam[i].len);cout<<ans;return 0;
}