字串與自動機
這些是比逐位比對更快的經典字串演算法。KMP 和 Z 函數能在線性時間內找出模式字串，Manacher 專門找回文，字串雜湊則能在常數時間內比較兩個子字串。
這是最小的一份題單，九章共 31 題：KMP、Z 函數、Manacher、字串雜湊、最小表示法、AC 自動機、後綴陣列與後綴自動機、子序列自動機，以及進階技巧。適合在題解裡看過這些名字、想拿真正的題目練練看的人。
31 題難度分 1167–26059 章節
進入書房
想要有人陪你寫完這份題單嗎？登入後進入書房，女主角會一次拿一道題目給你。
一、KMP（Prefix 的 Suffix）
§1.1 基礎
| 題目 | 難度分 |
|---|---|
| 28. 找出字符串中第一個匹配項的下標 | 未評分 |
| 796. 旋轉字符串 | 1167 |
| 1392. 最長快樂前綴 | 1876 |
| 1764. 通過連接另一個數組的子數組得到一個數組 | 1588 |
| 1668. 最大重複子字符串 | 1396 |
| 459. 重複的子字符串 | 未評分 |
| 2800. 包含三個字符串的最短字符串 | 1856 |
| 214. 最短迴文串 | 未評分 |
| 3529. 統計水平子串和垂直子串重疊格子的數目 | 2105 |
| 686. 重複疊加字符串匹配 | 未評分 |
| 3455. 最短匹配子字符串 | 2303 |
二、Z-Function（Suffix 的 Prefix）
§2.1 基礎
| 題目 | 難度分 |
|---|---|
| 2223. 構造字符串的總得分和 | 2220 |
| 3474. 字典序最小的生成字符串 | 2605 |
§2.2 LCP array
| 題目 | 難度分 |
|---|---|
| 2430. 對字母串可執行的最大刪除數 | 2102 |
三、Manacher Algorithm（Palindrome）
§3.1 基礎
| 題目 | 難度分 |
|---|---|
| 5. 最長迴文子串 | 未評分 |
| 647. 迴文子串 | 未評分 |
| 214. 最短迴文串 | 未評分 |
| 1745. 分割回文串 IV | 1925 |
§3.2 中心擴展法
| 題目 | 難度分 |
|---|---|
| 5. 最長迴文子串 | 未評分 |
| 2472. 不重疊迴文子字符串的最大數目 | 2013 |
四、String Hashing
§4.1 基礎
| 題目 | 難度分 |
|---|---|
| 28. 找出字符串中第一個匹配項的下標 | 未評分 |
| 187. 重複的 DNA 序列 | 未評分 |
| 1316. 不同的循環子字符串 | 1837 |
| 2261. 含最多 K 個可整除元素的子數組 | 1724 |
| 1044. 最長重複子串 | 2429 |
| 718. 最長重複子數組 | 未評分 |
五、最小表示法
§5.1 基礎
| 題目 | 難度分 |
|---|---|
| 899. 有序隊列 | 2097 |
| 1625. 執行操作後字典序最小的字符串 | 1992 |
七、Aho-Corasick Automaton
§7.1 基礎
| 題目 | 難度分 |
|---|---|
| 1032. 字符流 | 1970 |
| 1408. 數組中的字符串匹配 | 1223 |
八、Suffix Array/Suffix Automaton
§8.1 基礎
| 題目 | 難度分 |
|---|---|
| 1163. 按字典序排在最後的子串 | 1864 |
| 1754. 構造字典序最大的合併字符串 | 1829 |
| 1044. 最長重複子串 | 2429 |
| 718. 最長重複子數組 | 未評分 |
| 1408. 數組中的字符串匹配 | 1223 |
| 1316. 不同的循環子字符串 | 1837 |
九、Subsequence Automaton
§9.1 基礎
| 題目 | 難度分 |
|---|---|
| 792. 匹配子序列的單詞數 | 1695 |
十、其他
§10.1 進階
| 題目 | 難度分 |
|---|---|
| 466. 統計重複個數 | 未評分 |
這是階段一的最後一份題單，核心小節寫完後，路線就會進入需要遞迴的階段二。
難度分數來自 zerotrac 的 LeetCode 競賽評分。部分題目沒有 zerotrac 分數，會標示為「未評分」。
進入書房