提示

值域问题

• 若输入字符串只由小写字母组成，可以充分利用这个很小的值域（大小只有 \(26\)），比如将其作为一个常数加入算法：开 \(26\) 棵线段树；类似的，如果涉及到 int 的位运算，也可以使用这种技巧，比如：开 \(32\) 个树状数组。

两种算法的比较

• AC 自动机的题和 KMP 的题有一些本质的区别：
• • AC自动机因为要使用 Trie 树，因此字符的值域很小，KMP 则没有此限制；
• • AC 自动机用来匹配多模式串，一些 KMP 可以解决的问题在多模式串下也有可能能用AC自动机做。

Tricks of KMP

在使用 KMP 进行字符串匹配的过程中，可以附带求出许多别的东西，主要有下：

• 子串匹配：假设我们在字符串 \(s\) 中查找字符串 \(t\)，每当更新一次 \(i\) 的时候，我们就已经匹配了 \(t\) 的子串 \([0,j]\)（在 \(s\) 中的位置就是 \([i-j, i]\)）。因此我们通过枚举 \(t\) 的起点，就能找出 \(s\) 和 \(t\) 的公共子串。
• 公共前后缀：只有KMP的前半部分也是很好用的！pre 数组能快速查找出字符串任意前缀的最长相等前后缀。
• 周期问题：字符串的“周期”通常和 pre 数组有关。\((n-pre[n])\) 是最短周期的长度。（满足原字符串是将周期反复拼接多次得到的长字符串的一个前缀）
• 其他匹配问题可以转化为KMP：例如，两字符串内部各个字符之间的相等关系一样，通过维护每个字符左边最靠右的和它相等的字符的位置，将该“位置”做 KMP 匹配；若要满足各个字符在字符串中的排名相等，则维护其前缀中前驱和后继以及相等值的位置，将“位置”做 KMP 匹配。（见《题解》Y239）