欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

后缀自动机概述

程序员文章站 2022-04-30 18:21:35
...

如果对后缀自动机有一定了解,这几篇文章对你可能会有些许帮助:
menci’s后缀自动机学习笔记
后缀自动机学习指南
loj上的后缀自动机讲解
一些题目
听说对拆点讲解很详细
127~132周

以题目为主,当然也有一些讲解。下面说一下我对后缀自动机的理解,不给出详细证明。

后缀自动机的特点

首先,后缀自动机是一种有限状态自动机,他可以识别且仅识别一个字符串的后缀。但是这不并不是后缀自动机强大的地方,我可以说如果把AC自动机反向插入我同样可以做到这一点。

后缀自动机真正的用处在于:它可以识别一个串的所有子串。

非常优秀的是后缀自动机只会有O(n)个节点,也就是说在字符集看做常数的情况下,对于后缀自动机的构建可以做到O(n)

后缀自动机不同于AC自动机的地方在于:它并不是一棵树,不看prarent链的话,后缀自动机是一张DAG,这就让后缀自动机每一个节点的意义玄妙了起来。

后缀自动机每一个节点代表什么?

定义一个子串的所有出现位置结尾的集合为这个子串的right集合。
每一个节点识别的子串right集合相同,right集合相同的子串用同一个点接受。有一个很有意思的性质是right集合相同的字符串他们的长度一定是连续的。可以感性理解一下,aba和ba,aba出现的位置ba一定出现过,所以ba出现的位置数一定大于等于aba。

后缀自动机的parent链是什么?

如果B节点的right集合包含A节点right集合的最小集合,那么A节点有一条parent链连向B节点。可以把parent链当做fail链,但是他们之间有一些微妙的区别。
构造的意义:顺着parent链跳可以逐渐增大right集合以便找到所有可以转移的状态。
匹配的意义:我在匹配时记录已经匹配的长度,和当前在哪一个节点,那么我就可以知道我匹配最长是哪一个串,跳parent链时通过增大right集合,减小匹配长度,从而找到合法转移。这个等一会儿详细讲。
parent链是一棵树,它组成了原串反串的一棵后缀树(这里不研究后缀树)。

举个例子吧:abb

a:1
ab:2
b:2,3
bb:3
abb:3

我们把right集合相同的放在一起:
1,a
2,ab
3,b
4,abb,bb
把子集包含的连上parent链(红色代表parent链),这样我们就得到了一个后缀自动机:
后缀自动机概述
我们满足上面的条件就构造出了一个后缀自动机。
可以证明对于任意串满足上面的条件都可以构造一个后缀自动机。

如何构造一个后缀自动机?

后缀自动机是一个增量算法,也就是说已经构造出了s[1,i]的后缀自动机,现在要构造s[1,i+1]的后缀自动机。
对于每个节点记录一下它的转移,接受的最长串(len)和parent链(p),每次构造完之后记录一下到达的节点在哪儿(las)

加入的时候肯定要有一个节点接受整个串,新建点x的right集合为{i+1},同时赋值len=i+1。
right集合含有i的状态都可以转移到新建节点。发现las节点的right集合正好是i,根据上面的性质las节点的parent指向right集合包含i的节点,所以我们顺着las的parent链可以遍历所有right集合包含i的节点。

这些点都应该有一个向x的s[i+1]的转移。

下面分3种情况讨论:
1.如果顺着parent达到了空节点,那么所有right集合含有i的节点都增加了向x的一个转移。到达空节点即可结束。
2.到达了一个本来就有一个s[i+1]转移的节点y。设y向s[i+1]转移到q,那么right集合和q相同的子串已经被q接受,q的right集合是包含i+1最小集合,所以x的parent链连向p。
3.但是按照2的做法会有一个问题:
后缀自动机概述
这个后缀自动机是错误的,可以发现ab,b的right集合并不相同。
那究竟是什么情况让我们构造出了这样一个错误的自动机呢?
其实我们要让自动机新接受abb,bb,b三个串,并把它们分配给对应的节点,我们向前跳发现长度小于等于1的串(也就是b)已经被接受过了。q这个点的right集合里应该增加一个i+1。于是发现一个问题,q本来不止接受abb的后缀,它还多接受了一个串ab,ab的right集合并没有改变,但b改变了。本来right集合相同的串变成了不同的,但是我们用一个点接受,就产生了错误。
换一种说法,我们让x接受长度大于y的len+1的串,q接受[?,len+1]的串。但是q并不只接受[?,len+1]的串,q本来接受了一个长度大于len+1的串。这些长度大于len+1并不是y的转移,所以不是abb的后缀,这些串就不合法。
分情况讨论:

y的len+1 = q的len
这样按2的方法做。

y的len+1 < q的len
我们强行构造一个点让它接受[?,len+1]的串。我们用q复制一个点nq,nq的所有状态等于q的状态。沿着y的parent链向上找,把所有向q的转移转向nq。这样nq就接受了[?,len+1]的串的串,剩下的q就接受了[len+2,?]的串。q的parent链指向nq,x也指向nq。因为nq的riight集合包含q的和x的,所以把q和x的right集合指向nq。很显然,nq的len赋值为y的len+1

这样我们就构造了出了一个后缀自动机。

如何使用这个后缀自动机呢?

首先我们可以知道一个串是否作为模板串的子串出现过,因为这个自动机可以识别模板串的所有子串。这是后缀自动机的一个最简单的应用。

后缀自动机的强大之处在于:它可以计算每个子串出现次数。

怎么做?把非复制节点出现次数定为1,这个节点出现一次,它沿parent链向上的点都会出现一次。于是我们就可以求parent链的拓扑序向上递推。

每个点会有一个值,代表这个点管理的所有子串出现了那么多次。并且一个点x管理哪些子串呢?长度为(x的parent的len+1到x的len)。

这样我们就可以在后缀自动机里匹配了。就像AC自动机匹配即可。但是有一个问题,走到一个点时并不代表匹配了这个节点管理的所有字符串。所以我们需要额外记录一个表示当前匹配长度的变量。这个变量与x的len取一个较小值就好。

试一试吧:

找相同字符

写了这道题会对后缀自动机有一个大概理解,这里不赘述做法。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct lxy{
    int to[26],p,len,k,num;
}a[400005];

int cnt=1,las=1,len;
int tax[200005];
int tp[400005];
char s[200005];
long long ans;

void insert(int c,int w){
    a[++cnt].len=w;a[cnt].num=1;
    int i;for(i=las;a[i].to[c]==0&&i!=0;i=a[i].p) a[i].to[c]=cnt;
    las=cnt;
    if(i==0){
      a[cnt].p=1;return;
    }
    int q=a[i].to[c],nq;
    if(a[i].len+1==a[q].len){
      a[cnt].p=q;return;
    }
    nq=cnt+1;for(int j=i;a[j].to[c]==q;j=a[j].p) a[j].to[c]=nq;
    a[nq]=a[q];a[nq].num=0;a[nq].len=a[i].len+1;
    a[q].p=nq;a[cnt].p=nq;las=cnt;cnt++; 
}

void querytp(){
    for(int i=1;i<=cnt;i++) tax[a[i].len]++;
    for(int i=1;i<=len;i++) tax[i]+=tax[i-1];
    for(int i=1;i<=cnt;i++) tp[tax[a[i].len]--]=i;
}

void matchit(int u,int pos,int l){
    a[u].k++;ans-=1ll*a[u].num*(a[u].len-l);
    if(s[pos]==0) return;
    for(;a[u].to[s[pos]-'a']==0&&u!=0;u=a[u].p);
    if(u==0) matchit(1,pos+1,0);
    else matchit(a[u].to[s[pos]-'a'],pos+1,min(l,a[u].len)+1);
}

int main()
{
    scanf("%s",s+1);len=strlen(s+1);
    for(int i=1;i<=len;i++)
      insert(s[i]-'a',i);   
    querytp();
    for(int i=cnt;i>=1;i--) a[a[tp[i]].p].num+=a[tp[i]].num;
    scanf("%s",s+1);
    matchit(1,1,0);
    for(int i=cnt;i>=1;i--) a[a[tp[i]].p].k+=a[tp[i]].k,ans+=1ll*a[tp[i]].k*a[tp[i]].num*(a[tp[i]].len-a[a[tp[i]].p].len);
    printf("%lld",ans);
}

更多的题目可以参见文章开头的链接。