SAM复习

2018-04-10 23:15:32


最近想复习一遍SAM,然而发现 huntzhan.org/suffix-automaton-tutorial/ 这篇文章挂掉了,于是只能根据回忆自己推一遍了

大致记录一下自己推的思路。。防止以后又忘了。。

add(ch) :

新建一个np节点

last开始,每次沿着suffix link往回走,如果当前节点cur不存在ch的转移则将curch转移指向np

如果当前节点cur存在ch的转移,设转移到q

现在要做的事就是把q点存放的所有maxlen<=cur->maxlen+1的状态提取出来,将nplink指向被提取的这部分(不提取的话会导致状态重复)

如果q点的maxlen=cur->maxlen+1则不需要拆点,直接将nplink指向q,更新last指针,退出

否则新建一个节点nq,将q点的“较短”部分移动到nq里存放,更新nqnext(=q->next)、link(=q->link)和maxlen(=cur->maxlen+1)信息,把cur继续沿着link往回跳,将指向qch的转移改为指向nqqnplink指向nqlink,更新last指针,退出

这时剩余情况就是跳到根都找不到ch的转移,那么只需要把nplink指向根、更新last指针就好了

right集合大小可以先把所有前缀节点siz设为1,再在(对suffix link树)拓扑排序过程中树形$dp$出来

匹配时直接拿匹配串在sam上跑即可,最终位置的siz即为匹配次数

如果要匹配一个串的所有长度为k的子串,可以在匹配时维护一个curlen代表当前串长,若curlen>k则往回跳,并将curlen更新为跳完后节点的maxlen

如果只考虑匹配串长度为k的本质不同的子串,则可以在sam上记录每个节点是否被访问

我的节点命名方式可能和大家的不太一样,凑合看看就好了 $QAQ$

睡觉前写的,可能不知道自己写了些啥。。有时间自己再看一遍(

暂时不在uoj发出来,等第一页被填满再发。。