<总结>后缀自动机(SAM)

下标从1开始

引子

后缀自动机(SAM),即一个接受字符串所有后缀的最小DFA(确定性有限状态自动机),可以解决很多字符串相关的问题。

SAM最简单、也最重要的性质是,它包含关于字符串的所有子串的信息。依次记录任意从初始状态t_0开始的路径上每条转移边的字符会形成原串的一个子串 。反之原串的每个子串对应从状态t_0开始的某条路径。

概念

构成

  1. SAM是一张有向无环图
  2. SAM的每个节点为一个状态,每条边称作一个转移
  3. 转移上包含一个字符

endpos与等价类

endpos是一个子串在整个字符串出现的位置集合(位置为结尾所在下标),如abaabaabaa的endpos即{3, 6}(行内LaTeX打不出花括号嘤嘤嘤),而一些子串的endpos可能相同,这时我们把这些子串归为一个等价类,而SAM的每个节点代表一个等价类。

引理1:对于字符串的非空子串u, v(|u|\le|v|),如果endpos(u)=endpos(v),那么u在字符串中每次出现一定是以v的后缀形式存在的

显然

引理2:对于字符串的非空子串u, v(|u|\le|v|),要么endpos(u)\cap endpos(v)=\varnothing,要么endpos(v)\subseteq endpos(u)uv的后缀)

显然(真的!)

引理3:对于每个等价类,每个子串长度均不相同且连续,且较短子串均是较长子串的后缀

证明:

  1. 这个等价类只有1个子串:显然
  2. 这个等价类包含不止一个子串:
    1. 这里面如果有长度相同的串,因为其endpos相同,所以这两个子串会完全重合,不成立
    2. 考虑等价类里面最短的子串u,最长的子串v,以及不在这个等价类,但是u是其后缀,其是v后缀的子串w,那么endpos(u)\subseteq endpos(w)\subseteq endpos(v),又因为endpos(u)=endpos(v),所以endpos(u) = endpos(w) = endpos(v)
    3. 根据引理1,因为等价类中endpos相同,所以等价类中每个子串都是这个等价类中最长子串v的后缀。\quad\blacksquare

转移

我们通过转移链接每个状态。具体来说,对于一个等价类,我们在其后添加一个字符c,可以转移到一个新状态,也就是给一个等价类的每个子串的最后面添加一个字符,新的串中一些串不存在,另一些串构成了新的等价类。

后缀链接

这个并不是SAM里面的东西,但是非常有用。

考虑非起始状态的状态,其包含一些字符串的子串,而且这些子串都是后缀关系。接下来我们找到里面最短的子串u,然后找到包含u删掉开头一个字母的子串所在状态(肯定有一个——空串),我们把这个状态的后缀链接设为我们找到的这个状态。

引理4:SAM的后缀链接构成一棵树

证明:每个非空状态t的后缀链接链接到比其最短子串严格更短的子串所在的状态,最后一定到达空串所在状态t_0

所以,后缀链接构成的数就是endpos构成的树。

总结

构建了aabb的SAM,放图:

构造

光讲理论是没意义的。

对于每个节点,我们记录它包含子串的最大长度maxlen

构造步骤

  1. 我们先建立一个初始节点t_0,并设置为last = t_0trans(t_0) = t_?
  2. 对于在字符串末尾添加字符c,我们新建一个节点为t
  3. last开始通过link向上遍历节点,对于每个节点t_i,如果trans(t_i, c)为空,设置其为t
  4. 如果最后遍历到了t_?,设置link(t) = t_0,到10
  5. t_x = trans(t_i, c)
  6. 如果maxlen(t_x) = maxlen(t_i) + 1,设置link(t) = t_x,到10
  7. 建立一个节点t_c = t_xmaxlen(t_c) = maxlen(t_i) + 1,让trans(t_i, c) = t_c
  8. 设置link(t_x) = link(t) = t_c
  9. 继续从t_i跳后缀链接,并修改trans(t_i) = t_c,直到trans(t_i) \not= t_x
  10. 修改last = t

构造原理

约定:向字符串S添加字符c

  1. last跳后缀链接可以遍历S的所有后缀
  2. 步骤3的让endpos = endpos(S)的后缀添加字符到达endpos(S+c)的等价类
  3. 到达第5步后,我们设t_i对应的子串为T,那么我们发现endpos(T+c) \not=endpos(S+c)
    1. 如果maxlen(T+c) = maxlen(T) + 1,那么说明t_x状态只包含T+c及其后缀,对应图中情况1。那么我们直接将link(t) = t_x即可
    2. 如果maxlen(T+c) \not= maxlen(T) + 1,那么说明maxlen(T+c) > maxlen(T) + 1,说明状态t_x不止包含上述子串,还有其他更长的子串,对应图中情况2。我们必须要把这个状态分成两个状态t_x(长度大于maxlen(T) + 1的)和t_c(长度小于等于maxlen(T)+1的),然后让trans(t_i) = t_c
    3. 我们第一步只是复制了状态,当然新状态trans是不用修改的,没问题,见图;但是link(t_x) = t_c,稍微想一想也是对的
    4. 最后我们要修改后缀链接上trans(t_i) = t_xtrans,原因:这些被选出的状态都是S的后缀,他们的trans(c)指向t_x是因为T+c,我们要保证他们加上c指向的状态都指向T+c及其后缀所在的状态,现在t_x已经不包含这些状态了。

最后贴上结构体指针版本的代码(喂指针真的更适合用来看吧)

inline void insert(Node *from, Node *to, int v)
{//from: last    to: this    v: char
    to->maxlen = from->maxlen + 1;
    for (; from && from->trans[v] == nullptr; from = from->link)
        from->trans[v] = to;
    if (from == nullptr)
    {
        to->link = nd;
        return;
    }
    Node *x = from->trans[v];
    if (from->maxlen + 1 == x->maxlen)
    {
        to->link = x;
        return;
    }
    Node *c = pool_++;
    memcpy(c->trans, x->trans, sizeof c->trans);
    c->maxlen = from->maxlen + 1;
    c->link = x->link;
    x->link = to->link = c;
    for (; from && from->trans[v] == x; from = from->link)
        from->trans[v] = c;
}

对于长度为n的字符串,时间复杂度O(n),不分析(OI wiki请),对于节点数量来说的话,上界为2n+1,理由是初始有一个节点,每次加入一个字符需要一个新节点,还可能产生一个复制节点。

关于实际应用,请看分类目录:后缀自动机

点赞

发表评论

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