SAM复习

最近想复习一遍SAM，然而发现 huntzhan.org/suffix-automaton-tutorial/ 这篇文章挂掉了，于是只能根据回忆自己推一遍了 大致记录一下自己推的思路。。防止以后又忘了。。 ` add(ch)` : 新建一个`np`节点 从`last`开始，每次沿着suffix link往回走，如果当前节点`cur`不存在`ch`的转移则将`cur`的`ch`转移指向`np` 如果当前节点`cur`存在`ch`的转移，设转移到`q`点 现在要做的事就是把`q`点存放的所有`maxlen<=cur->maxlen+1`的状态提取出来，将`np`的`link`指向被提取的这部分（不提取的话会导致状态重复） 如果`q`点的`maxlen=cur->maxlen+1`则不需要拆点，直接将`np`的`link`指向`q`，更新`last`指针，退出 否则新建一个节点`nq`，将`q`点的“较短”部分移动到`nq`里存放，更新`nq`的`next`(`=q->next`)、`link`(`=q->link`)和`maxlen`(`=cur->maxlen+1`)信息，把`cur`继续沿着`link`往回跳，将指向`q`的`ch`的转移改为指向`nq`，`q`和`np`的`link`指向`nq`的`link`，更新`last`指针，退出 这时剩余情况就是跳到根都找不到`ch`的转移，那么只需要把`np`的`link`指向根、更新`last`指针就好了 `right`集合大小可以先把所有前缀节点`siz`设为`1`，再在（对`suffix link`树）拓扑排序过程中树形$dp$出来 匹配时直接拿匹配串在sam上跑即可，最终位置的`siz`即为匹配次数 如果要匹配一个串的所有长度为`k`的子串，可以在匹配时维护一个`curlen`代表当前串长，若`curlen>k`则往回跳，并将`curlen`更新为跳完后节点的`maxlen` 如果只考虑匹配串长度为`k`的本质不同的子串，则可以在`sam`上记录每个节点是否被访问 我的节点命名方式可能和大家的不太一样，凑合看看就好了 $QAQ$ 睡觉前写的，可能不知道自己写了些啥。。有时间自己再看一遍（ 暂时不在uoj发出来，等第一页被填满再发。。