后缀自动机

我又来学后缀自动机啦

后缀自动机是个能够识别一个字符串的所有后缀的自动机。但由于任何一个子串都是一个后缀的前缀,所以实际上它能识别任何一个子串。

后缀自动机的概念很多,为防止造成思维混乱,在此不引入,只是通俗地介绍后缀自动机的实现和用法,至于正确性、复杂度分析和证明,在此就不赘述,有兴趣可以膜拜陈老师的冬令营论文。

构造

后缀自动机的构造是增量构造,即每次仅加入一个字符。也就是说,它支持在末尾新增字符。

后缀自动机的每个结点表示的可能是后缀相同的多个字符串。每个结点和AC自动机一样有两种指针,一种表示读入某个字符后能够达到的状态;一种是指向表示它表示的串中最短者的次长后缀。后者就相当于AC自动机中的\(fail\)指针。一个结点表示一个串当且仅当从根节点依次读入每个字符会走到该点。

不过和AC自动机很大的不同就在于它的一个结点可能表示多个串,所以不同的几个结点可能连向了同一个结点。同时也正因如此,后缀自动机的结点个数是O(n)的。通过其构造的方式我们观察到可以这一点。

每次加入一个字符,我们新建一个结点\(np\)表示当前整个字符串。

然后从表示加这个字符之前的字符串的结点\(p\)开始(也就是上一次的\(np\)),不断跳\(fail\)链直到找到一个有该字符出边的结点。那么之前走过的结点表示的串在后面加这个字符得到的串一定在字符串中都是第一次出现。所以边走边从这些结点连一条边到\(np\)即可。

第一种情况,若一直找到根节点都没有,就可以结束了。但如果找到了这样的一个结点\(p\),它加上这个字符走到了\(q\),那么此时又有两种情况:

  1. \(q\)表示的串只有一个,那么显然\(q\)一定是\(np\)的后缀,并且也可以确定是次长后缀,所以可以将\(np\)的\(fail\)直接指向\(q\);
  2. \(q\)表示的串包括\(np\)的次长后缀\(sq\)和一些其他以\(sq\)为后缀的串。这时我们需要把\(sq\)分离出来。那么我们新建一个结点\(nq\)表示串\(sq\),由于它是原来的\(q\)中最短者,所以它的所有指针仍然继承\(q\)的,并且易知此时\(q\)和\(np\)的\(fail\)都指向它。最后将所有连向\(q\)的边转连向\(nq\)即可。

举个简单的例子:构建字符串\(aabb\)的后缀自动机

首先后缀自动机只有一个点,加入第一个字符\(a\):

符合第一种情况。

接着加入第二个字符\(a\):

此时找到了\(p\)能加\(a\)走到\(q\)。因为\(q\)表示的串仅有一个\(a\),所以符合第二种情况,直接将\(np\)的父亲指向\(q\)。

接着加入第三个字符\(b\):

符合第一种情况。

加入第四个字符\(b\):

此时我们发现\(p\)加上\(b\)能走到\(q\),而\(q\)代表的串有\(b\)和\(ab\)两个,符合第三个条件。

于是新建一个点\(nq\),按上述方法重新连边即可。

每次最多新建两个点,所以点数是\(O(n)\)的。边数也是\(O(n)\)的,在此不给出证明。因此后缀自动机的构造是\(O(n)\)的。

如何实现维护一个点表示了多少个串?令\(len_i\)表示\(i\)结点表示的串中的最长者\(s_i\)的长度,那么\(i\)表示的串就是所有的长度大于\(len_{fail_i}\)的\(s_i\)的后缀。很显然\(i\)表示的串的个数就是\(len_i-len_{fail_i}\)。

当我们建好了后缀自动机后,它的\(fail\)树上的每个点的父亲表示的串都是它表示的串的后缀。因此我们可以给每个点定义一个\(right\)集合,表示字符串中所有出现了该串的位置的右端点的集合。

那么很显然,对于所有成为过\(np\)的结点,它们表示的串是原串的某个前缀,可以先将该前缀的右端点放入该结点。其它结点的\(right\)集合如果要包括这一右端点,该结点一定表示这个点的一个后缀,也就是\(fail\)树上的一个祖先。于是沿\(fail\)树向上统计即可。

例题

那么这个后缀自动机就可以识别所有子串了。怎么用它做题呢?

给出几个经典的题目(详细题解请点击进入):

SPOJ1811 求两个串的最长公共子串

SPOJ1812 求多个串的最长公共子串

BZOJ3998 求给定串的第\(k\)小子串

UOJ35 求字符串的后缀数组

后缀自动机的很多应用都包含在上面几题的题解中了。

说点什么

5 评论 在 "后缀自动机"

提醒
排序:   最新 | 最旧 | 得票最多
成员

第一个资瓷!

成员

%

游客

%

游客

%

游客

泥又在刷火题

wpDiscuz