后缀自动机
自动机
首先什么是自动机
我们大多用的是\(DFA\),也就是有限状态自动机
整个自动机是由一些边和点组成的,边上的权为字符
简单理解就是输入一个字符串如果是我们想要接受的，那这个字符串就会按顺序遍历图,并最后会在终止节点停下,是为接受
当然,也有一些字符串无法被接受,比如AC自动机就是接受模式串
后缀相关
我们将以\(i\)为结尾的所有子串建一棵\(Tire\)
很明显这样的\(Tire\)点数是\(n^2\)的,同时它可以接受所有子串的功能
而后缀自动机就是最小化上述的自动机
为了缩小点数,我们可以对一些具有相同性质的点缩点
定义\(R_S\)为子串\(S\)在原串中所有出现位置的右端点组成的集合,我们把相同\(R\)的子串缩成一个点
然后探究一下这样做的正确性与性质
首先对于\(R_X\)与\(R_Y\),如果两者有交集,则一定是包含或被包含的关系
考虑反证,如果存在\(R_X,R_Y\)有交集,在交集的位置,我们假设\(|X|>|Y|\),则\(Y\)是\(X\)的一个子串
对于\(pos\in R_X,\notin R_Y\),其\(|Y|\)一定能在\(pos\)位置匹配到,则\(R_Y\subseteq R_X\)
由此,我们定义\(Link\)表示当前节点\(i\)代表\(R\),\(Link_i\)为\(R\subseteq R'\)最小的\(R'\),也就是从\(R'\)这里选一些子集
注意到\(Link\)形成的是一个树的结构,同时每次连边会划分集合至少两个,因此点数保证一定是\(2*n\)左右
注意区分自动机上的连边和\(Link\)边
自动机的连边是在当前子串\(S\)上加一个字符\(ch\)后\(S+ch\)能匹配到所有的右端点,相当于在后面加字符
而\(Link\)边是为了放大\(R\),相当于在前缀删字符最多删多少,同时注意到一个节点代表的是一段连续的区间,因为删字符得到的前缀一定是连续的,如果设\(Len_i\)表示\(i\)点代表字符串的最长长度,那么\(i\)代表的区间为\([Len_{link_i}+1,Len_i]\)
具体实现
后缀自动机的实现是在线的
记当前末尾位置为\(Lp\),字符为\(ch\)
具体的我们考虑记录\(Last\)表示之前自动机末尾停下的节点,\(cur\)为当前末尾的节点,\(cur\)肯定是连在\(Last\)的后面,边为\(ch\),同时\(Len_{cur}=Len_{Last}+1\)
考虑跳\(Last\)字符串的前缀也就是跳\(Link\)链,假设现在跳到了节点\(P\)如果\(P\)没有\(ch\)边,则直接给它连到\(cur\)
找到第一个有\(ch\)边的\(P\),走\(ch\)边后为\(Q\),如果没找到直接\(Link_{cur}=0\)
考虑如果\(Len_Q=Len_P+1\),则\(P\)接\(ch\)等同于\(Q\)就可以了,\(Link_{cur}=Q\),同时\(Q\)的\(Link\)链上的\(R\)全部插一个\(Lp\)(没必要实现)
如果\(Len_Q>Len_P+1\)，则\(Q\)对应的子串比\(P+ch\)更长,即在\(Link\)树上\(P+ch\)为\(Q\)的父亲,我们复制\(Q\)到\(Clone\),直接\(Link_Q=Link_{cur}=Clone\),同时我们继续爬\(Last\)的\(Link\)链,将所有指向\(Q\)的全部指向\(Clone\)
struct SAM{
SAM_node Tree[MAXN*2];
int cnt_node;
int Last;
void Build()
{
cnt_node=0;
Last=0;
Tree[0].Link=-1;
Tree[0].Len=0;
return;
}
void Insert(char s)
{
int p=Last;
int cur=++cnt_node;
p=Tree[Last].Link;
Tree[Last].Next[s-'a']=cur;
Tree[cur].Len=Tree[Last].Len+1;
while((p!=-1)&&(!Tree[p].Next[s-'a']))
{
Tree[p].Next[s-'a']=cur;
p=Tree[p].Link;
}
if(p==-1)
{
Tree[cur].Link=0;
}
else
{
int q=Tree[p].Next[s-'a'];
if(Tree[q].Len==Tree[p].Len+1)
{
Tree[cur].Link=q;
}
else
{
int clone=++cnt_node;
Tree[clone]=Tree[q];
Tree[clone].Len=Tree[p].Len+1;
Tree[q].Link=clone;
Tree[cur].Link=clone;
while((p!=-1)&&(Tree[p].Next[s-'a']==q))
{
Tree[p].Next[s-'a']=clone;
p=Tree[p].Link;
}
}
}
Last=cur;
}
}sam;
一些应用
首先明确一些性质
根节点到每个点的所有路径拼起来就是这个点代表的字符串集合
\(R\)的大小就是这个点出现节点的次数,同时\([Len_{Link_i}+1,Len_i]\)是\(i\)代表节点的长度区间
不同字符串的个数及总长度
考虑每个点的贡献分别为\(Len_i-Len_{Link_i}\)和\(\dfrac{(Len_i+1+Len_{Link_i})(Len_i-Len_{Link_i})}{2}\)
出现次数
每个节点的出现次数就是\(|R|\),我们在插入的时候就在终止节点插一个元素,维护即可
K子串
预处理一下当前节点为起点有多少条路径然后贪心即可
#include <bits/stdc++.h>
const int MAXN = 1e6 + 5;
using namespace std;
struct SAM_node {
int Len;
int Next[26];
int Link;
int num;
};
struct SAM {
SAM_node Tree[MAXN * 2];
int cnt_node;
int T;
vector<int>g[MAXN * 2];
vector<int>G[MAXN * 2];
int Rd[MAXN * 2];
long long Dp[MAXN * 2];
int Last;
void Build() {
cnt_node = 0;
Last = 0;
Tree[0].Link = -1;
Tree[0].Len = 0;
return;
}
void Insert(char s) {
int p = Last;
int cur = ++cnt_node;
p = Tree[Last].Link;
Tree[Last].Next[s - 'a'] = cur;
Tree[cur].Len = Tree[Last].Len + 1;
while ((p != -1) && (!Tree[p].Next[s - 'a'])) {
Tree[p].Next[s - 'a'] = cur;
p = Tree[p].Link;
}
if (p == -1) {
Tree[cur].Link = 0;
} else {
int q = Tree[p].Next[s - 'a'];
if (Tree[q].Len == Tree[p].Len + 1) {
Tree[cur].Link = q;
} else {
int clone = ++cnt_node;
Tree[clone] = Tree[q];
Tree[clone].num = 0;
Tree[clone].Len = Tree[p].Len + 1;
Tree[q].Link = clone;
Tree[cur].Link = clone;
while ((p != -1) && (Tree[p].Next[s - 'a'] == q)) {
Tree[p].Next[s - 'a'] = clone;
p = Tree[p].Link;
}
}
}
Last = cur;
Tree[cur].num++;
}
void Link_Build() {
for (int i = 0; i <= cnt_node; i++) {
if (Tree[i].Link != -1) {
g[Tree[i].Link].push_back(i);
}
for (int j = 0; j <= 25; j++) {
if (!Tree[i].Next[j]) {
continue;
}
G[Tree[i].Next[j]].push_back(i);
Rd[i]++;
}
}
}
void dfs(int x) {
for (int i = 0; i < g[x].size(); i++) {
int v = g[x][i];
dfs(v);
Tree[x].num += Tree[v].num;
}
}
void Topsort() {
queue<int>q;
for (int i = 1; i <= cnt_node; i++) {
if (!Rd[i]) {
q.push(i);
}
if (!T) {
Dp[i] = 1;
} else {
Dp[i] = Tree[i].num;
}
}
while (q.size()) {
// printf(">?");
int temp = q.front();
q.pop();
for (int i = 0; i < G[temp].size(); i++) {
int v = G[temp][i];
Rd[v]--;
Dp[v] += Dp[temp];
if (Rd[v] == 0) {
q.push(v);
}
}
}
}
void Rank(int k) {
int p;
for (int i = 0; i <= 25; i++) {
if (!Tree[0].Next[i]) {
continue;
}
int Pox = Tree[0].Next[i];
if (Dp[Pox] < k) {
k -= Dp[Pox];
} else {
printf("%c", i + 'a');
p = Pox;
break;
}
}
while (1) {
// printf("???");
int Kp;
if (!T) {
Kp = 1;
} else {
Kp = Tree[p].num;
}
if (k <= Kp) {
break;
} else {
k -= Kp;
}
for (int i = 0; i <= 25; i++) {
if (!Tree[p].Next[i]) {
continue;
}
int Pox = Tree[p].Next[i];
if (Dp[Pox] < k) {
k -= Dp[Pox];
} else {
printf("%c", i + 'a');
p = Pox;
break;
}
}
}
}
} sam;
string S;
int T;
int k;
int main() {
cin >> S;
sam.Build();
for (int i = 0; i < S.size(); i++) {
sam.Insert(S[i]);
}
scanf("%d %d", &T, &k);
sam.T = T;
sam.Link_Build();
sam.dfs(0);
sam.Topsort();
sam.Rank(k);
}
最小循环移位
首先如果存在循环位移,最小循环节长度应该为\(N-Next[N]\)
证明考虑匹配的是\([1,Next[N]]\)段,你将这一段移一下去正好相等
这启示我们直接建\(S+S\)的后缀自动机,在上面找一个与原串相等且右端点最小的即可(相比于KMP空间有点大)
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
const int MAXN=1e6+5;
using namespace std;
struct SAM_node{
int Len;
int Next[26];
int Link;
int min_num;
};
int Lit;
struct SAM{
SAM_node Tree[MAXN*2];
vector<int>g[MAXN*2];
int cnt_node;
int Last;
void Build()
{
cnt_node=0;
Last=0;
Tree[0].Link=-1;
Tree[0].Len=0;
return;
}
int New()
{
++cnt_node;
for(int i=0;i<26;i++)
{
Tree[cnt_node].Next[i]=0;
}
Tree[cnt_node].Link=0;
Tree[cnt_node].min_num=0x3f3f3f3f;
Tree[cnt_node].Len=0;
return cnt_node;
}
void Insert(char s,int Pos)
{
int p=Last;
int cur=New();
p=Tree[Last].Link;
Tree[Last].Next[s-'a']=cur;
Tree[cur].Len=Tree[Last].Len+1;
while((p!=-1)&&(!Tree[p].Next[s-'a']))
{
Tree[p].Next[s-'a']=cur;
p=Tree[p].Link;
}
if(p==-1)
{
Tree[cur].Link=0;
}
else
{
int q=Tree[p].Next[s-'a'];
if(Tree[q].Len==Tree[p].Len+1)
{
Tree[cur].Link=q;
}
else
{
int clone=++cnt_node;
for(int i=0;i<26;i++)
{
Tree[clone].Next[i]=Tree[q].Next[i];
}
Tree[clone].Link=Tree[q].Link;
Tree[clone].min_num=0x3f3f3f3f;
Tree[clone].Len=Tree[p].Len+1;
Tree[q].Link=clone;
Tree[cur].Link=clone;
while((p!=-1)&&(Tree[p].Next[s-'a']==q))
{
Tree[p].Next[s-'a']=clone;
p=Tree[p].Link;
}
}
}
Last=cur;
if(Pos>Lit)
{
Tree[cur].min_num=min(Tree[cur].min_num,Pos);
}
}
void Link_Build()
{
for(int i=0;i<=cnt_node;i++)
{
g[i].clear();
}
for(int i=0;i<=cnt_node;i++)
{
if(Tree[i].Link!=-1)
{
g[Tree[i].Link].push_back(i);
}
}
}
void dfs(int x)
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
dfs(v);
Tree[x].min_num=min(Tree[v].min_num,Tree[x].min_num);
}
}
int Find(string S)
{
int P=0;
for(int i=0;i<S.size();i++)
{
P=Tree[P].Next[S[i]-'a'];
}
return Tree[P].min_num;
}
}sam;
char SS[MAXN];
string S;
int T;
int k;
int main()
{
while(1)
{
cin >> SS;
S = string(SS, SS+strlen(SS));
if(S[0]=='.')
{
break;
}
Lit=S.size();
sam.cnt_node=0;
sam.Build();
for(int i=0;i<S.size();i++)
{
sam.Insert(S[i],i+1);
}
for(int i=0;i<S.size();i++)
{
sam.Insert(S[i],(i+1)+(int)S.size());
}
sam.Link_Build();
sam.dfs(0);
int Pd=sam.Find(S);
if(Pd==0x3f3f3f3f)
{
printf("1\n");
}
else
{
int Lp=(Pd-(S.size()));
printf("%d\n",int((S.size())/Lp));
}
}
}
第一次出现的位置
很明显维护每一个节点\(R\)集合的最小值
所有出现的位置
维护对应节点的\(R\)即可,大概要用启发式合并？
其实直接遍历子树就行了
最短的没有出现的字符串
一个很zz的问题,就是一层一层的找到第一个连边没有覆盖到所有字符集的节点
两个字符串的最长公共子串
假设有两个串为\(S,T\)
我们对\(S\)建\(SAM\),考虑\(T\)的前\(i\)为的匹配的最长后缀,答案明显显然为最大值
然后考虑优化这个过程,把\(T\)前\(i\)的字符串放进\(SAM\)匹配最长后缀,设当前匹配到\(p\),长度为\(l\)
添加\(T_{i+1}\),如果\(p\)有连边就直接走,否则跳\(Link\)链找第一个满足的
多个字符串的最长公共子串
考虑沿用上道题的思路
同样这样匹配,我们计算在当前\(S_i\)的匹配中节点能匹配的最长长度
而每个节点在多个匹配中的答案显然是每次匹配的最小值
至于最长长度,从\(Link\)树上\(dfs\)即可
#include<bits/stdc++.h>
const int MAXN=1e5+5;
using namespace std;
struct SAM_node{
int Len;
int Next[26];
int Link;
};
struct SAM{
SAM_node Tree[MAXN*2];
int cnt_node;
vector<int>g[MAXN*2];
int Last;
int mx[MAXN*2];
int mi[MAXN*2];
int Flag_Isbuild;
void Build()
{
cnt_node=0;
Last=0;
Tree[0].Link=-1;
Tree[0].Len=0;
return;
}
void Insert(char s)
{
if(!Flag_Isbuild)
{
Flag_Isbuild=1;
Build();
}
int p=Last;
int cur=++cnt_node;
p=Tree[Last].Link;
Tree[Last].Next[s-'a']=cur;
Tree[cur].Len=Tree[Last].Len+1;
while((p!=-1)&&(!Tree[p].Next[s-'a']))
{
Tree[p].Next[s-'a']=cur;
p=Tree[p].Link;
}
if(p==-1)
{
Tree[cur].Link=0;
}
else
{
int q=Tree[p].Next[s-'a'];
if(Tree[q].Len==Tree[p].Len+1)
{
Tree[cur].Link=q;
}
else
{
int clone=++cnt_node;
Tree[clone]=Tree[q];
Tree[clone].Len=Tree[p].Len+1;
Tree[q].Link=clone;
Tree[cur].Link=clone;
while((p!=-1)&&(Tree[p].Next[s-'a']==q))
{
Tree[p].Next[s-'a']=clone;
p=Tree[p].Link;
}
}
}
Last=cur;
}
void LinkB()
{
for(int i=0;i<=cnt_node;i++)
{
if(Tree[i].Link==-1)
{
continue;
}
g[Tree[i].Link].push_back(i);
}
}
void dfs(int x)
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
dfs(v);
mx[x]=max(mx[x],mx[v]);
}
mx[x]=min(mx[x],Tree[x].Len);
mi[x]=min(mi[x],mx[x]);
}
}sam;
bool cmp(string x,string y)
{
return x.size()<y.size();
}
string S[15];
int main()
{
//freopen("date.in","r",stdin);
// freopen("rnm.out","w",stdout);
int Cnt;
scanf("%d",&Cnt);
for(int i=1;i<=Cnt;i++)
{
cin>>S[i];
}
sort(S+1,S+1+Cnt,cmp);
for(int i=0;i<S[1].size();i++)
{
sam.Insert(S[1][i]);
}
sam.LinkB();
for(int i=0;i<=sam.cnt_node;i++)
{
sam.mi[i]=0x3f3f3f3f;
}
for(int C=2;C<=Cnt;C++)
{
int p=0;
int l=0;
int Ans=0;
for(int i=0;i<=sam.cnt_node;i++)
{
sam.mx[i]=0;
}
for(int i=0;i<S[C].size();i++)
{
if(sam.Tree[p].Next[S[C][i]-'a'])
{
p=sam.Tree[p].Next[S[C][i]-'a'];
l++;
}
else
{
while((p!=-1)&&(!sam.Tree[p].Next[S[C][i]-'a']))
{
p=sam.Tree[p].Link;
l=sam.Tree[p].Len;
}
if(p==-1)
{
p=0;
l=0;
}
else
{
p=sam.Tree[p].Next[S[C][i]-'a'];
l++;
}
}
sam.mx[p]=max(l,sam.mx[p]);
}
sam.dfs(0);
}
int Ans=0;
for(int i=sam.cnt_node;i>=1;i--)
{
Ans=max(Ans,sam.mi[i]);
}
printf("%d\n",Ans);
}