什么是后缀自动机

温馨提醒:以下概念比较晕人,请保持耐心.

后缀自动机是一个有向无环图,节点为状态,有向边为状态转移。其中有一个初始状态可以到达所有状态,若干个结束状态,从初始状态走到一个结束状态,就是原本字符串的一个后缀
可接受节点:若p是一个可接受节点,那么从root到p的每条路径上的字符组成的字符串,都是当前串的一个后缀。因此,在加入一个新字符时,这个节点后面可以连一个新节点,增长后缀。
儿子:每个节点可以直接到达的节点
right集合:当前状态表示的子串的终点集合,或者说,由于后缀自动机有一个性质,在上面随便走几步得到的是原串的子串,而走到这个节点终止,可以是哪些子串.
pre指针:某个节点的上一个代表字符与其相同的可接受节点,或者说,是当前节点代表的子串一个right集合会变大的后缀.十分类似于AC自动机的fail指针.
step:从根节点到某个节点最多要走的步数,或者说,是其可控的最长长度(妈呀说不清了QAQ,理解为这个节点可代表这些子串吧)
重要定理:假如字符x的上一位是字符y,插入x后,每个代表字符是y的可接受节点后面都应该接上新点。

是不是看得很晕?那么看个栗子.
字符串”abaabab”中,对于子串”ab”,其right集合应该是$\{ 2,5,7 \}$,而b的right集合是$\{ 2,5,7 \}$,所以如果一个节点可控制子串”b”,也一定能控制”ab”,因而该节点可控制长度为1和2,它的step为2.
在由pre指针构成的pre树上,每一个节点的子节点的right集合的并集就是该节点的right集合.并且某个节点的可控制子串长度应该和其pre呈连续关系,比如说,如果某一个节点可控制子串长度为3到8,那么其pre的可控长度应为2或1和2,而不可能为1.
因而,一个节点可代表的子串数量为$right[x] \times (step[x]-step[pre[x]])$
abbb的后缀自动机大约如图所示:
灵魂画手litble

如何构造后缀自动机

建议静下心来,结合后面的代码进行理解。
假设现在已经构建好了前len个字符的后缀自动机(前len个字符组成的串称为当前串),我们要插入一个新字符x进去,那么我们要实行“三步走”的发展战略
1.建立一个新节点np
2.找到之前最后一个建立的节点last,那么last一定是一个可接受节点。顺着last的pre指针依次往上跳,这些节点一定也是可接受节点。所以如果这些节点没有x儿子,那么就让它们的x儿子为np
代码表示如下:

while(!ch[p][x]) ch[p][x]=np,p=pre[p];

3.跳到某一个节点p,它有x儿子了。怎么办?
p的x儿子为q,分两种情况:
  3-1.如果$step[q]=step[p]+1$,这时,从根节点出发到q,一定会经过p,且中间不夹杂其他字符。由重要定理,p的后面应该接上一个x,那么可以将q视作这个x,而当前x对应的节点一定会是可接受节点,所以q就成了一个可接受节点。因此,令$pre[np]=q$即可。
  代码表示:

if(step[q]==step[p]+1) pre[np]=q;

  3-2.如果$step[q]> step[p]+1$。由于这种情况不太好处理,所以我们可以将其转化为3-1
  具体做法是新建一个节点nq代替q强行使得$step[nq]=step[p]+1$。那么将q的儿子指针和pre指针都拷贝给nq,然后(准确来说是最后一步)顺着ppre指针往上走,将那些x儿子是q的节点的x儿子都改成nq。
  那么nppre就是这个代替了q的nq啦~\(≧▽≦)/
  而由于和3-1中的q是可接受节点一样的原因,nqq都是可接受节点,所以qpre指针指向nq
  代码表示:

int nq=++cnt;step[nq]=step[p]+1;
for(int i=0;i<26;++i) ch[nq][i]=ch[q][i];
pre[nq]=pre[q],pre[q]=pre[np]=nq;
while(ch[p][x]==q) ch[p][x]=nq,p=pre[p];

完整版代码:

void ins(int x) {
    int p=last,np=++cnt;
    last=np,step[np]=step[p]+1;
    while(p&&!ch[p][x]) ch[p][x]=np,p=pre[p];
    if(!p) pre[np]=1;
    else {
        int q=ch[p][x];
        if(step[q]==step[p]+1) pre[np]=q;
        else {
            int nq=++cnt;step[nq]=step[p]+1;
            for(int i=0;i<26;++i) ch[nq][i]=ch[q][i];
            pre[nq]=pre[q],pre[q]=pre[np]=nq;
            while(ch[p][x]==q) ch[p][x]=nq,p=pre[p];
        }
    }
}

后缀自动机的基本应用

现在我们造出了一台后缀自动机,我们要把它应用于生产实践之中了!
后缀自动机的几个性质:
性质1:从root出发在上面瞎走几步,可以得到一个子串。而且如果走完所有走法,那么可以得到所有子串。
性质2:后缀自动机是一个有向无环图,可以进行拓扑排序。
性质3:出现次数向父亲传递,接收串数从儿子获取
由以上两个性质,我们会发现后缀自动机上可能经常要求递推和dp。
以下基本上是clj的ppt上的例题=_=
洛谷P3804:由pre指针的定义,可知用pre指针相连的节点在原串中可以视作同一字符,所以按照拓扑序逆序处理子串的出现次数,而子串长度就是step。
sz指的是pre树上以该节点为根的子树的大小,因为每个节点的right集合在pre树上是其子树right集合的并集,所以sz就是right集合的大小.

void getans() {
    for(int i=1;i<=cnt;++i) ++b[step[i]];
    for(int i=1;i<=cnt;++i) b[i]+=b[i-1];
    for(int i=1;i<=cnt;++i) a[b[step[i]]--]=i;
    for(int i=cnt;i>=1;--i) {
        sz[pre[a[i]]]+=sz[a[i]];
        if(sz[a[i]]>1) ans=max(ans,1LL*sz[a[i]]*step[a[i]]);
    }
}

spoj-NSUBSTR:用上一题的方法获得sz值就可以了。
bzoj2555:使用lct去维护上面的sz值……码力不足的本蒟蒻调试了三个小时……
poj1509:把字符串复制一份贴到后面,然后插入到后缀自动机里,由性质1,从根节点出发走length(字符串长度)步即可获得最小字典序循环节。
因为我们是走了length步到达当前节点的,所以当前节点的step一定大于等于length。假设step不代表这个节点的字符在字符串中的位置,那么一定存在一个和当前这个长度为length的子串长得一样的串,在当前子串的前面。这样我们找到的就应该是那个串的结束节点,与假设矛盾。所以step代表这个节点的字符在字符串中的位置,答案是$step[p]-length+1$
SPOJ – SUBLEX:注意,并不是在任何情况下step都代表这个节点的字符在字符串中的位置(本蒟蒻就因为这个WA了……)
令$dp$表示从这个节点往后还能生成多少子串,逆拓扑序计算一遍后就很好处理了。
spoj-LCS:对于字符串A建立后缀自动机,然后用B去遍历该自动机。如果走到某个节点,它有x儿子,就走到x儿子,当前匹配长度+1。否则顺着pre指针往上找到一个有x儿子的节点p,当前匹配长度为step[p]+1,再走到p的x儿子。如果找不到,就走到根,匹配长度为0。
spoj-LCS2:对于第一个字符串建立后缀自动机,然后用其他字符串去用上题类似方法遍历。
我们令g:以该节点代表的字符结尾的子串,在本次匹配中的最大匹配长度,f:每次用一个新字符串去后缀自动机里匹配的g的最小值。
显然答案是所有f里的最大值。
注意的是,在后缀自动机上,某节点的匹配结果也应该是它的pre的匹配结果,所以还要更新pre。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
char s[N>>1];
int ch[N][26],pre[N],step[N],a[N],b[N],f[N],g[N];
int cnt,last,len,now,nl,ans;
void ins(int x) {
    int np=++cnt,p=last; last=np,step[np]=step[p]+1;
    while(!ch[p][x]&&p) ch[p][x]=np,p=pre[p];
    if(!p) pre[np]=1;
    else {
        int q=ch[p][x];
        if(step[q]==step[p]+1) pre[np]=q;
        else {
            int nq=++cnt; step[nq]=step[p]+1;
            for(int i=0;i<26;++i) ch[nq][i]=ch[q][i];
            pre[nq]=pre[q],pre[q]=pre[np]=nq;
            while(ch[p][x]==q) ch[p][x]=nq,p=pre[p];
        }
    }
}
void topsort() {
    for(int i=1;i<=cnt;++i) ++b[step[i]];
    for(int i=1;i<=cnt;++i) b[i]+=b[i-1];
    for(int i=1;i<=cnt;++i) a[b[step[i]]--]=i;
    for(int i=1;i<=cnt;++i) f[i]=step[i];
}
int main()
{
    scanf("%s",s),len=strlen(s);
    cnt=last=1;for(int i=0;i<len;++i) ins(s[i]-'a');
    topsort();
    while(~scanf("%s",s)) {
        len=strlen(s),now=1,nl=0;
        for(int i=1;i<=cnt;++i) g[i]=0;
        for(int i=0;i<len;++i) {
            int x=s[i]-'a';
            if(ch[now][x]) now=ch[now][x],g[now]=max(g[now],++nl);
            else {
                while(now&&!ch[now][x]) now=pre[now];
                if(!now) now=1,nl=0;
                else nl=step[now]+1,now=ch[now][x],g[now]=max(g[now],nl);
            }
        }
        for(int i=cnt;i>=1;--i) {
            int p=a[i];
            if(pre[p]) g[pre[p]]=max(g[pre[p]],g[p]);
            if(f[p]>g[p]) f[p]=g[p];
        }
    }
    for(int i=2;i<=cnt;++i) ans=max(f[i],ans);//不要算根,没有意义
    printf("%d",ans);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

4 条评论

yyb · 2018年2月26日 7:41 下午

此评论已被litble手动折叠
折叠原因:含有虚假信息

    konnyakuxzy · 2018年2月26日 8:47 下午

    Orz您太强了
    233333
    手动折叠
    膜拜litble是传播虚假信息哈哈哈哈
    笑死了QvQ

    litble · 2018年2月26日 8:53 下午

    Orz您太强了

konnyakuxzy · 2018年1月9日 8:51 下午

Orz太强了,都学后缀自动机了
我三兄弟还一个都不会,,,
赶紧学习惹QAQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *