后缀自动机

后缀自动机(Suffix Automation, SAM)是一种能够接受所有源串后缀的最简的DFA(确定性有限状态自动机).他的定义使得他具有以下性质:

  • 最简
  • 是一个有向无环图(DAG),点之间的单向边即为字符的转移
  • 有且仅有源串的所有子串可以在这张图上走到一个节点,一个节点可能对应多个子串,这些子串的各个结束位置完全一致
    (这些字符串接下来的任何转移均完全相同.为了最简,这些状态会被合并)
  • 时间、空间复杂度均在\(O(n)\)级别(这个需要证明)

如非特殊说明,下文中一切下标均从\(1\)开始.

定义

  • 我们把代表任意空串的开始节点叫做\(\text{root}\)节点.
  • 我们定义一个子串的\(\text{Right}\)集合表示他在源串中出现时的所有结束位置所组成的集合.
  • 可能有多个子串能够同时到达一个节点,他们的\(\text{Right}\)集合一定完全相同.我们定义一个节点的\(\text{Right}\)集合为这个集合.
    定义\(\text{root}\)的\(\text{Right}=\{1,2,3,\cdots,Len\}\),即空串在所有地方都出现.
  • 我们定义一个(不是\(\text{root}\))\(u\)节点的上级节点\(v\)(称为\(\text{Prev}\))为满足\(\text{Right}(v)\supsetneqq\text{Right}(u)\)且\(\text{Right}\)集合最小的结点.
  • 观察发现(接下来就会观察),一个节点表示的许多子串一定是某个子串的长度连续的后缀(接下来再来理解),我们称其中的最长长度为\(\text{MaxLen}\),最短长度为\(\text{MinLen}\)
  • 最后再定义\(\text{Step}\)为从根节点到一个节点的步数.

我们接下来举一个例子,以便理解:\[\large\text{qaq}\color{Blue}\underbrace{\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}}\color{Black}\text{ov}\color{Fuchsia}\overbrace{\color{Fuchsia}\text{o}\color{Blue}\underbrace{\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}}}\color{Black}\text{qwq}\color{OrangeRed}\text{efg}\]

在上面的例子中,蓝色的\(\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}\color{Black},\color{Blue}\text{cd}\color{OrangeRed}\text{efg}\color{Black},\color{Blue}\text{d}\color{OrangeRed}\text{efg}\)节点相同,他们的\(\text{Right}=\{9,18\}\),大小是\(2\).他们的子串长度\(\in\{4,5,6\}\),所以对应节点有\(\text{MaxLen}=6,\text{MinLen}=4\).我们称这个节点为\(p\).

当子串进一步变小时,新的\(\color{OrangeRed}\text{efg}\)在其他地方也有出现,这使得\(\color{OrangeRed}\text{efg}\)的\(\text{Right}\)变大,变成了\(\{9,18,\color{OrangeRed}24\color{Black}\}\).如果子串再继续变小,\(\text{Right}\)有可能继续变大,所以必须有一个新节点,称为\(q\),并且有\(\text{Prev}(p)=q\).这使得我们发现了一条规律:

  • 节点\(\text{Prev}(u)\)对应的\(\text{MaxLen}\)长度恰为节点\(u\)的\(\text{MinLen}\)减\(1\).

当子串向前变长时,新的\(\color{Fuchsia}\text{o}\color{Blue}\text{bcd}\color{OrangeRed}\text{efg}\)出现的位置减少了,\(\text{Right}\)集合变成了\(\{18\}\).同时,这个节点的\(\text{Prev}\)是\(q\).

构造

SAM的构造采用增量法,即将源串的字符从左到右一个一个加到SAM中.现在考虑\(\text{SAM}(S)\)到\(\text{SAM}(S+c)\)的变化,其中\(S\)是字符串,\(c\)是新加入的字符.

首先,我们上一次加入的结点\(last\)一定会连向\(c\),所以我们新建一个结点\(u\),连到\(last\)的\(c\)字符出边中,且让\(\text{Step}(u)=\text{Step}(last)+1\);在对\(last\)不断求\(\text{Prev}\)的过程中,只要当前节点没有\(c\)的出边,这个节点就需要向\(u\)连一条字符为\(c\)的出边.

如果我们在这个过程中一直走到了\(\text{root}\)都没有遇到出边\(c\),那么这个新节点\(u\)的\(\text{Prev}(u)\)的子串只能是无所不在的空串了.\(\text{Prev}(u)\)置为\(\text{root}\).(接下来的举例都是其上面的情况)\[\large\text{qwq}\color{Blue}\text{efgh}\color{Black}\text{q}\color{Blue}\text{efgh}\color{Black}\text{aq}\color{Blue}\text{efgh}\color{Fuchsia}\text{c}\]

如果遇到了有\(c\)出边的点,我们就称其为\(p\),同时称\(p\)的\(c\)出边指向的节点为\(q\).接下来有两种情况可供讨论:

如果\(\text{Step}(q)=\text{Step}(p)+1\),那么之前出现的q和现在的\(p+c\)一定是一样的(\(p+c\)指从\(p\)节点向\(c\)边转移一步).这样,我们直接把\(\text{Prev}(u)\)置为\(q\)即可.\[\large\text{qw}\overbrace{\color{Blue}\text{efgh}\color{BlueViolet}\text{c}}^{q}\color{Black}\text{ovo}\color{Blue}\text{efgh}\color{Black}\text{qaq}\color{Blue}\text{efgh}\color{Fuchsia}\text{c}\]

否则,\(q\)在\(p\)之前还会有其他在\(last\)中没有出现的字符,\(q\)和\(p+c\)一定不是等价的.在这种情况下,我们为\(p+c\)这个节点新建一个节点,称为\(v\).\(v\)在子串的意义上是\(q\)的后缀,他的\(\text{Right}(v)=\text{Right}(q)+\{\text{Len}(S+c)\}\)(多了当前加进去的最后位置),所以我们应该把\(v\)的所有出边从\(q\)那里复制过来(当前源串的最后还没有出边),并且使得\(\text{Step}(v)=\text{Step}(p)+1,\text{Prev}(v)=\text{Prev}(q),\text{Prev}(q)=v\),最后有\(\text{Prev}(u)=v\).\[\large\underbrace{\color{Red}\text{ijkl}\color{Black}\normalsize\overbrace{\color{Blue}\text{efgh}}^{p}\color{BlueViolet}\text{c}}_{\color{Black}q}\color{Black}\text{qaq}\underbrace{\color{Red}\text{ijkl}\color{Black}\normalsize\overbrace{\color{Blue}\text{efgh}}^{p}\color{BlueViolet}\text{c}}_{\color{Black}q}\color{Black}\text{q}\overbrace{\color{Blue}\text{efgh}}^{p}\color{Black}\text{wq}\underbrace{\normalsize\overbrace{\color{Blue}\text{efgh}}^{p}\color{Fuchsia}\text{c}}_{v}\]

应用

我也不会啊……等会了再写

发表评论

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