字元串

字元串已經忘光了,隻好花了一天時間來複習

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]\) 的範圍，是以需要限定最大值。畫圖之後翻折過去就能了解。

字尾數組

不會