字符串

字符串已经忘光了,只好花了一天时间来复习

kmp

一篇好的讲解

kmp模板

code：

ac自动机

trie树上的kmp

将多个模式串上trie树，一个文本串来匹配模式串。

fail 类似于 kmp 的 nxt

概括 ac自动机 求 fail 的过程： 1.对整个字典树进行宽度优先遍历。 2.若当前搜索到点 \(x\)，那么对于 \(x\) 的第 \(i\) 个儿子（也就是代表字符 \(i\) 的儿子），一直往 \(x\) 的 fail 跳，直到跳到某个点也有 \(i\) 这个儿子，\(x\) 的第 \(i\) 个儿子的 fail 就指向这个点的儿子 \(i\)。

形式上，ac 自动机基于由若干模式串构成的 trie 树，并在此之上增加了一些 fail 边；本质上，ac 自动机是一个关于若干模式串的 dfa（确定有限状态自动机），接受且仅接受以某一个模式串作为后缀的字符串。 并且，与一般自动机不同的，ac 自动机还有 关于某个模式串的接受状态，也就是与某个模式串匹配（以某个模式串为后缀）的那些状态，即某个模式串在 trie 树上的终止节点在 fail 树上的整个子树。

ac自动机模板

code:

manacher

入门时的博客

注意其中对于 \(hw_i\) 初始化部分，<code>hw[i]=min(hw[(mid&lt;&lt;1)-i],hw[mid]+mid-i);</code>

其中 <code>hw[mid]+mid-i</code> 等价于 <code>maxright-i​</code> 这实际上是 \(i\) 在 \(mid\) 左边相对应的 \(j\) 所受的限制，因为 \(hw_j\) 可能会超出 \(mid-hw[mid]\) 的范围，所以需要限定最大值。画图之后翻折过去就能理解。

后缀数组

不会