【后缀自动机sam学习小记】

定义

顾名思义，后缀自动机就是可以识别原串所有后缀的自动机，最后回到达叶子状态，同时也可以识别所有连续子串。

时间复杂度

线性。由构造方法可知点数是线性的。构出sam后除了主链，即代表原串的链，其他的边要么就是构成了一个新的后缀，要么就是连接若干条构成了一个新的后缀的边，形成一个类似树的结构，所以边也是线性的。

各种东西的意义

很多性质都由定义得出，理解定义就可以发现很多性质。

right

一个字符串的right集即出现这个字符串[l,r)的所有r的集合。

能走到sam上同一个节点的字符串right集一定相同，一个节点的right集即任意一个能到达当前节点的字符串的right集。

right集只有包含与被包含或无交集，当r相同时增大l，right集不会减小。

fa

即parent，就是最小的right集，包含当前right集。

mx

使当前right集合法的最大长度，可以发现，使当前right集合法的最小长度即fa的mx加1。

构造

考虑上一个加入的字符所代表的点p，当前要加入的字符所代表的点np，新建一条p=>np的边，mx[np]=mx[p]+1，这个比较显然，其实就是当前字符串的长度。

考虑找p的fa，找到第一个由当前字符转移的点q，类似于ac自动机跳fail，找到最大的right集包含当前的right集，且包含当前字符转移的，对之前的点都连一条到np的边。由连边方式可以发现当前p的所有fa都一定有当前字符转移的边。

设p连出去的点为q，当mx[p]+1==mx[q]时可以发现q是由p直接转移过来的，可以直接加上当前字符，把np的fa设为q即可。当mx[p]+1！=mx[q]时可以发现p到q之间经过了多于一个字符，我们必须新建状态来表示当前情况，设这个点为nq，可以发现nq的mx比q的mx小，即right集较大，而p的mx比nq的mx小，即right集较大。所以q是nq的子集，nq是q的子集，fa[q]=nq,fa[nq]=p,fa[np]=nq,mx[nq]=mx[p]+1>

同时我们要处理nq的转移，可以发现q的转移和nq一样，而之前转移到q的状态就要先转移到nq，这个很容易证明。至此我们就完成了sam的构造。

应用

sam的应用很灵活，体现在它自动机的特性和parent树，还有right集的各种特性，具体的例子留坑待填。

code

例题链接

#include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define ULL unsigned long long #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const mn=5*1e5+9,mp=1e6+9,inf=1e9+7; int t,K,n,pon,f[mp],g[mp],son[mp][26],fa[mp],mx[mp],du[mp],qu[mp]; char s[mn]; int main(){ //freopen("string.in","r",stdin); //freopen("string.out","w",stdout); freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%s",s+1);n=strlen(s+1); fo(i,1,n)s[i]-='a'; scanf("%d%d",&t,&K); int last=pon=1; fo(i,1,n){ int p=last,np=last=++pon; mx[np]=mx[p]+1;f[np]=1; for(;p&&(!son[p][s[i]]);p=fa[p])son[p][s[i]]=np; if(!p){fa[np]=1;continue;} int q=son[p][s[i]]; if(mx[p]+1==mx[q])fa[np]=q; else{ int nq=++pon;mx[nq]=mx[p]+1; fa[nq]=fa[q]; fa[np]=fa[q]=nq; fo(j,0,25)son[nq][j]=son[q][j]; for(;p&&(son[p][s[i]]==q);p=fa[p])son[p][s[i]]=nq; } p=np; } fo(i,1,pon)du[fa[i]]++; int he=0,ti=0; fo(i,1,pon)if(!du[i])qu[++ti]=i; while(he!=ti){ int now=qu[++he],next=fa[now]; du[next]--; f[next]+=f[now]; if(!du[next])qu[++ti]=next; } if(!t)fo(i,1,pon)f[i]=1; fo(i,1,pon)g[i]=f[i]; fo(i,1,pon)fo(j,0,25)du[son[i][j]]++; he=0,ti=0; qu[++ti]=1;du[0]++; while(he!=ti){ int now=qu[++he]; fo(i,0,25){ int next=son[now][i]; du[next]--; if(!du[next])qu[++ti]=next; } } fd(i,ti,1)fo(j,0,25){ int now=qu[i],next=son[now][j]; if(next)g[now]+=g[next]; } int now=1; if(K>g[1]){printf("-1");return 0;} while(1){ fo(i,0,25){ int next=son[now][i]; if(!next)continue; if(g[next]<K)K-=g[next]; else{ printf("%c",'a'+i); K-=f[next]; now=next; if(K<=0)return 0; break; } } } return 0; }