后缀自动机
性质
一个起点若干个终点。原串所有子串与从起点开始的路径一一对应，不重不漏
每个点包含若干子串。且这些子串一定是里面最长子串的连续后缀
SAM要考虑的边
- 普通边。相当于在某个状态表示下添加一个字符
- Link,father。表示将该状态表示的最短子串删除首字符。这类边构成一棵树
构造
endpos(s)：子串所有出现的位置的(尾字母下标)的集合。SAM每个状态都一一对应一个endpos等价类endpos的性质：
- 若s1是s2的后缀，则endpos(s1)包含endpos(s2)
- 两个不同的子串，要么包含关系，要么交集为空
- 两个子串endpos相同，短串为长串的后缀
- 如果两个子串endpos相同，那么他们之间的串也属于当前集合
问题
- 如何求不同子串的数量？
对于每个点，求max[i]-min[i]+1的总和，max[i]在构造的时候维护，min[i]=max[j]+1j为Link连向的边 - 每个子串的出现次数？
endpos的集合大小
模板
cpp
LL f[N];//f为endpos的集合大小
vector<int> adj[N];
struct SAM{
struct Node{
int len,link;
array<int,26> ne;
Node():len{},link{},ne{}{}
};
//最多2n-1个节点，3n-4条边
vector<Node> t;
int lst;
SAM(){
init();
lst=1;
}
void init(){
t.assign(2,Node());
}
int newNode(){
t.emplace_back();
return t.size()-1;
}
int extend(int p,int c){
if(t[p].ne[c]){
int q=t[p].ne[c];
if(t[q].len==t[p].len+1)return q;
int r=newNode();
t[r]=t[q];
t[r].len=t[p].len+1;
t[q].link=r;
while(p&&t[p].ne[c]==q){
t[p].ne[c]=r;
p=t[p].link;
}
return r;
}
int cur=newNode();
lst=cur;
t[cur].len=t[p].len+1;
while(p&&!t[p].ne[c]){
t[p].ne[c]=cur;
p=t[p].link;
}
if(!p)t[cur].link=1;
else t[cur].link=extend(p,c);
return cur;
}
int extend(int p,char c,char offset='a'){
return extend(p,(int)c-offset);
}
int next(int p,int c){
return t[p].ne[c];
}
int next(int p,char c,char offset='a'){
return next(p,(int)c-offset);
}
int link(int p){
return t[p].link;
}
int len(int p){
return t[p].len;
}
int size(){
return t.size();
}
};
LL ans=0;
SAM sam;
void dfs(int u){
for(auto v:adj[u]){
dfs(v);
f[u]+=f[v];
}
if(f[u]>1)ans=max(ans,sam.len(u)*f[u]);
}
void solve(){
string s;
cin>>s;
for(auto c:s){
int tmp=sam.extend(sam.lst,c);
f[tmp]=1;
}
for(int i=2;i<sam.size();i++)adj[sam.link(i)].push_back(i);
dfs(1);
cout<<ans<<"\n";
}最长公共子串
- 对第一个串建后缀自动机
- 对于每个串，寻找以i开头对应的最长串的自动机节点，标记
- 每次处理完一个串后，还要更新它的link节点的串
- 处理完所有串后，对所有节点的最长长度取max
cpp
struct SAM{
struct Node{
int len,link;
array<int,26> ne;
Node():len{},link{},ne{}{}
} t[N];
//最多2n-1个节点，3n-4条边
int lst=1,tot=1;
SAM(){
init();
}
void init(){}
int newNode(){
++tot;
return tot;
}
int extend(int p,int c){
if(t[p].ne[c]){
int q=t[p].ne[c];
if(t[q].len==t[p].len+1)return q;
int r=newNode();
t[r]=t[q];
t[r].len=t[p].len+1;
t[q].link=r;
while(p&&t[p].ne[c]==q){
t[p].ne[c]=r;
p=t[p].link;
}
return r;
}
int cur=newNode();
lst=cur;
t[cur].len=t[p].len+1;
while(p&&!t[p].ne[c]){
t[p].ne[c]=cur;
p=t[p].link;
}
if(!p)t[cur].link=1;
else t[cur].link=extend(p,c);
return cur;
}
int extend(int p,char c,char offset='a'){
return extend(p,(int)c-offset);
}
int next(int p,int c){
return t[p].ne[c];
}
int next(int p,char c,char offset='a'){
return next(p,(int)c-offset);
}
int link(int p){
return t[p].link;
}
int len(int p){
return t[p].len;
}
int size(){
return tot+1;
}
};
vector<int> adj[N];
int now[N],ans[N],res;
SAM sam;
void dfs(int u){
for(auto v:adj[u]){
dfs(v);
now[u]=max(now[u],now[v]);
}
}
void solve(){
string s;
cin>>s;
for(auto c:s)sam.extend(sam.lst,c);
for(int i=1;i<sam.size();i++)adj[sam.link(i)].push_back(i),ans[i]=sam.len(i);
while(cin>>s){
memset(now,0,sizeof now);
int p=1,t=0;
for(int i=0;i<s.size();i++){
int c=s[i]-'a';
while(p>1&&!sam.next(p,c))p=sam.link(p),t=sam.len(p);
if(sam.next(p,c))p=sam.next(p,c),t++;
now[p]=max(now[p],t);
}
dfs(1);
for(int i=1;i<sam.size();i++)ans[i]=min(ans[i],now[i]);
}
for(int i=1;i<sam.size();i++)res=max(res,ans[i]);
cout<<res<<"\n";
}回文自动机dp
题意：
问多少次操作能到大目标串
- 操作一：在首或尾添加一个字符
- 操作二：将逆串放进队尾
思路：
- 操作二越多越好，记一个回文串为 ,
- 假设v是u的儿子，则 ,构成回文串u之前加入一个字符，最后翻转得到v
- 记小于等于 一半的最长回文后缀为 ,,先构造一半再翻转
cpp