首页 > 笔记 > 广义后缀自动机总结

广义后缀自动机总结


我们在做后缀自动机的题目的时候,都是对一个串构造后缀自动机,那么该如何对多个串建出后缀自动机呢?

那就是广义后缀自动机。首先我们考虑一个暴力的建造方法,就是每次建完一个串以后就把last指针移到root上面,接着建下一个串。

发现时间复杂度其实依旧是$O(n)$,而且匹配也不会出现啥问题。

但是这样新加入一个点的时候可能已经有这个转移了,那该怎么办呢?

其实和后缀自动机的建法是一样的,首先看max集合是不是等于pre的max+1,假如等于的话这个节点就已经很合适了,而且Parent都找好了,就不用进行其他的操作了。

不等于的话还是需要新建一个辅助节点,而且我们已经找好了它的Parent,就是这个点的Parent。

当然,我们可以忽视不用创建节点的情况,每次都创建一个节点,后果就是有可能它的max跟它的父亲相同,这样没有状态能转移到它,它也不表示任何一个子串,它存在的意义只是为它的祖先贡献了的right集合一个位置,当然它在parent树中还必须起一个连接作用。代码可以完全不改变。

而按照最简状态后缀自动机的定义,这种状态是不应该存在的,但是存在的话问题也不大。因为空间其实最大就是2n的。。

下面就是构建代码

现在就做了两个题

bzoj3926

bzoj2780


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×