manacher 和扩展KMP

2024-08-28 05:06:44

manacher 和扩展KMP

事实上，这两个东西是一样的。

考虑 manacher 的过程

我们实时维护最远扩展的位置 \(mx\) 以及这个回文串的回文中心 \(l\) ，那么显然当然位置如果没有超过 \(mx\)

，是可以利用与 \(l\) 的对称位置 \(2l-i\) 的信息的，然后判断一下是否可以延伸 \(mx\) 的位置

也可以出一些有意思的东西

给你一个长为 \(n\) 的串的 \(2n+1\) 的回文数组 \(pa\) ，求哪些字符是相等的。

拿并查集维护的话，有一种类似于萌萌哒那个题倍增做法，但是多一个 \(\log\)

但是如果考虑 manacher 的过程，其实本质不同的相等位置只会在 \(mx\) 扩展的时候出现，就可以优化掉这个 \(\log\)

考虑扩展KMP

给你 \(s,t\) ，要求你求出 \(t\) 与 \(s[i,n]\) 的所有 \(lcp\)

其实可以转换到求 \(s[i,n]\) 与 \(s[1,n]\) 的 \(lcp\)

同样维护 \(lcp\) 最远扩展的位置 \(mx\) 以及这个 \(lcp\) 的起始位置 \(l\) ，那么当前如果没有超过\(mx\) ，位置 \(i\) 可以利用 \(i-(l-1)\) 与 \(s\) 的 \(lcp\) ，并判断是否可以扩展

可以发现和上面是一个东西的，写起来也差不多

最新文章

热门文章