SAM

sam,后缀自动机复习。

待更新。

会过sam,但是忘了,网上教程像是一步一步喂你饭真心很烦。。。

还是得自己写一写,上次自学的时候总结了一些,但那时候还觉得别的写的可能好一点,真是巨大错误。。。


\(endpos\rightarrow right\) 集合。

\(fail\rightarrow parent\)​ 树。

\(right\) 集合中最大的长度 \(l\)

注意sam的构造方式是增量构造,你需要管插入的串的正确性,其余的自然正确。

插入一个字符,我们需要把以这个字符为结尾的所有串插入parent树。

为了描述简单易懂现在往 i 位,插入 c,字符串记为 s。

首先,从上一个最后的后缀往上跳,看dag什么时候有 c 的出边。

注意parent 树跳父亲本质在缩短后缀。

  1. 如果没有,那么新建节点 w,parent树父亲是根,相当于把 s[k:i] \(k\leq n\) 全部插入,用 w代替了。

    然后把刚才跳过的父亲的 c 出边全连到 w。

    考虑刚才跳父亲本质上在跳插入前串的后缀。

  2. 否则设当前 dag 有 c 出边的点为 d,\(trans(d,c)=x\)

    那么尽管 d 是原串一个后缀,x 也有可能不是仅仅是新加入后缀,而有可能比新加入的要长。

    eg: c='b',d="aaa",x="ccaaab"。

    这个 x是要比我们插入 c 后的后缀 "aaab" 长,也就是说我们新加入的 \(right\) 集合更大应该做父亲。

    所以我们就判断一下 \(l(d)\)\(l(x)\) 的关系。

    1. 如果 \(l(d)=l(x)+1\)​ 那么就是插入后后缀和 x 长度一样,不用当爹,直接新建节点 w,按照 1那样把符合的新状态在 dag 上连边。w 在 parent 树上直接认 x 为爹。

      本质上在把一部分后缀直接插入,作为 w,剩下的都是原自动机可以表示的。

    2. 否则 \(l(d)<l(x)+1\) 我们必须把这个 x 所在的 \(right\) 拆开。

      我们就把集合 \(right_x\)​​​ 拆成 \(A=\{d+c\}\)​​​ 和 \(B=\{k\in right_x\mid length(d+c)<length(k)\}\),注意 \(length\) 含义是字符串长度​​​​ 。

      同理新建 w,dag 连新边,w 认 \(A\) 为爹,\(B\)\(A\) 为爹。

      注意 A,B dag 连边情况和 x 一样,还有记得把以前dag向 x 连边的改成向 A 连边。

      本质上在把一部分后缀直接插入,作为 w;特殊独立出来 d+c 这个后缀;然后别的也是原先自动机可以表示,只不过多了点改边操作。

注意我们一个个插入后缀本质上是把所有字串都插入了。

注意:每一个parent树上结点,可以对应一个dag上结点,为什么,考虑我们往字符串后加字符,这些后缀不会发生改变。


构造SA。

主要通过做法理解正确性。

反串的parent树就是后缀树。

构造SA呢,就是建出反串后缀树,然后考虑一个 rightpos 中最长的串,他的儿子都是相当于在原串中加后缀

而且

这些串加的第一个字符必定互不相同。我们只需要维护这个串第一次是在哪个后缀被加入的,就能简单地维护出该位字符时什么。

所以他们的字典序可以很好排出。

仔细想一下反串后缀自动机每一次都是加后缀反串。然后考虑parent树每一次跳前缀,进而sort


SAM
https://proton-z.github.io/2022/08/30/review-sam/
作者
Imitators
发布于
2022年8月30日
许可协议