后缀自动机(suffix-automaton, SAM)用一种高压缩的方式存储了文本串的所有子串信息,其中最重要的信息是状态结点,转移和后缀连接。下图表示字符串banana
的后缀自动机,其中红色虚线代表后缀连接。
关于后缀自动机的一些性质可以从上面的实例中得以体现:
接下来说一下后缀自动机的构造方法。
假设当前已经构造好了 S[1…n] 的后缀自动机,当我们新增添 c=S[n+1] 的时候,需要考虑 n+1 个新的后缀。设上一次新增字符增添的结点为 last,这次肯定要新增加一个新的结点 cur,否则字符串 S[1…n+1] 就无法表示。令 p 沿着 last 的后缀路径遍历,如果 trans[p][c](转移)不存在,那么令 trans[p][c]=cur,否则跳出。如果一直到 S 仍然转移不存在,最后令 link[cur]=S,否则假设第一个存在 trans[p][c] 的结点是 u,trans[u][c]=v,就要分两种情况讨论了:
构造代码如下(构造仅仅是 extend 那一部分,所有数组从1开始):
// 1号是S结点 const int maxn=1e6+5; struct suffix_automaton { int maxlen[maxn<<1],trans[maxn<<1][26],link[maxn<<1],tot=1,last=1; int endnum[maxn<<1],c[maxn<<1],a[maxn<<1]; int e[maxn<<1]; void extend(int c) { int cur=++tot,p; endnum[cur]=1; maxlen[cur]=maxlen[last]+1; for(p=last;p && !trans[p][c];p=link[p]) trans[p][c]=cur; if(!p) link[cur]=1; else { int q=trans[p][c]; if(maxlen[q]==maxlen[p]+1) link[cur]=q; else { int clone=++tot; maxlen[clone]=maxlen[p]+1; memcpy(trans[clone],trans[q],sizeof(trans[q])); for(;p && trans[p][c]==q;p=link[p]) trans[p][c]=clone; link[clone]=link[q]; link[q]=link[cur]=clone; } } last=cur; } void get_endpos_num() // count the end-position number of every node(state) { REP(i,1,tot) c[maxlen[i]]++; REP(i,1,tot) c[i]+=c[i-1]; REP(i,1,tot) a[c[maxlen[i]]--]=i; REP_(i,tot,1) endnum[link[a[i]]]+=endnum[a[i]]; } void get_end() // get the end node(state) { for(int i=last;i!=1;i=link[i]) e[i]=1; } void build(char *s,char minc) { for(int i=0;s[i];i++) extend(s[i]-minc); get_endpos_num(); //get_end(); } };
后缀自动机的时间复杂度和空间复杂度都是 O(n) 。
关于后缀自动机的一些常见应用:
一些题目:
就是可以处理多个字符串后缀信息的后缀自动机,据说是一种Trie+SAM的结构,但是以下的做法一般来说也没什么问题:
一些例题: