之前学过一次 \(kmp\) 但是已经差不多忘光了，现在重新来温习一遍 \(kmp\)。
首先 \(kmp\) 能在 \(O(n + m)\) 的时间复杂度内完成字符串匹配，他重要的思想就是避免了不必要的匹配。看下面这样一张图。
可以发现我们在第 \(6\) 个位置失配了，按照暴力的做法，我们会将模式串往后移一位，然后将匹配指针挪回来再一位位匹配。这样会有很多没必要的匹配，于是我们想，能不能有一个办法让匹配指针不断右移而不回挪，这样我们的复杂度就可以达到线性了，事实上办法是有的。不难发现我们需要将模式串往后挪到一个位置使得匹配指针前的所有字符刚好全部能匹配上，也就是我们要找到一段公共前后缀，将模式串移到这样的后缀开始的以一个位置上即可。但是公共前后缀有这么多，如果要记录所有公共前后缀，显然这样复杂度还是 \(O(n ^ 2)\) 的，那么我们要做的就是找到移动到一个最合适的位置，使得这个位置和上个位置直接不存在匹配。
考虑这样一个事情，如果这一次的到的位置和上一次位置之间存在一个匹配，那么在这个匹配位置的公共前后缀长度一定会比当前的大，那么如果我们选择这次跳到最长公共前后缀的位置，那么这中间就不会存在匹配了，那么接下来的任务就在于如何求出最长公共前后缀。
首先明确一点，我们要求的是模式串 \(1 \sim i\) 一段子串的最长公共前后缀，我们令其为 \(nxt_i\)。我们拿模式串去和自己匹配，不难发现对于一个位置 \(i\) 为了求出的公共前后缀最长，因此就要尽可能在模式串前缀中多匹配一些位置。假设我们现在要求 \(1 \sim i\) 的最长公共前后缀，因为已经求出了 \(i - 1\) 的答案，假设以 \(i - 1\) 为结尾的后缀最多能匹配 \(1 - j\) 的前缀，即在模式串 \(j + 1\) 的位置失配，如果 \(S_i = S_{j + 1}\) 那么显然有 \(nxt_i = nxt_{i - 1} + 1\)。否则我们就可以一直跳 \(nxt\) 即 \(j = nxt_j\) 直到 \(S_i = S_{j + 1}\)，因为 \(nxt\) 是最长公共前后缀的长度，因此每次模式串后移的长度是最短的并且在这中间不会存在一个位置使得前缀后缀能够匹配，那么这部分求 \(nxt\) 就做完啦！
代码如下：
nxt[0] = nxt[1] = 0;
for(int i = 2, j = 0; i <= m; ++i){
while(s2[j + 1] != s2[i] && j) j = nxt[j];
if(s2[j + 1] == s2[i]) ++j; //特判没有公共前后缀的情况
nxt[i] = j;
}
for(int i = 1, j = 0; i <= n; ++i){
while(s2[j + 1] != s1[i] && j) j = nxt[j];
if(s2[j + 1] == s1[i]) ++j; //特判一位都不能匹配的情况
if(j == m) printf("%d\n", i - j + 1);
}
实际上 \(kmp\) 能做的事 \(Hash\) 也能做，真正用处非常大的是 \(kmp\) 的 \(nxt\) 数组，尤其是在与循环节有关的问题中非常有用。下面给出 \(nxt\) 数组的一些性质。
-
一个字符串存在循环节当且仅当 \(n - nxt_n \mid n\)
首先我们可以证明如果 \(n - nxt_{n} \mid n\) 那么是一定有循环节的。
首先假设 \(S_{1, nxt_n}\) 是上图中的绿色部分，其他颜色分别是长度为 \(x\) 的块，因为 \(S_{1, n - nxt_n} = S_{nxt_n + 1, n}\) 那么相同颜色块应该相同，又根据在原串中的位置可以得到绿色块和黄色块相同，同理又可以得到黄色块和红色块相同，以此类推可以得到原串是个循环串。
下面来证明对于 \(n - nxt_{n} \nmid n\) 的情况不存在循环节。
首先考虑 \(nxt\) 数组的定义，不难发现有 \(S_{1, nxt_n} = S_{n - nxt_n + 1, n}\)，那么类似于第一种做法循环节的证明方法，可以发现 \(S_{1, n - nxt_n}\) 也可以在原串中循环只是不能刚好循环完毕，即最后一次循环只能出现部分。我们称这种循环节为伪循环节。
首先令 \(x = n - nxt_n\)，假设存在一个长度为 \(len\) 的循环节，显然 \(len \ne x\)。首先如果 \(len < x\)，那么显然 \(nxt_n\) 可以变大，矛盾。如果 \(x \mid len\) 既然 \(len\) 都能循环那么 \(x\) 一样能循环，矛盾。对于 \(x \nmid len\) 的情况，因为 \(x \nmid len\) 那么一定存在一个伪循环节会跨过第一个循环节和第二个循环节，假设这个伪循环节是第 \(k\) 个，那么 \(S_{len + 1, len + x} = S_{1, x} = S_{k \times x + 1, (k + 1) \times x}\) 可以发现 \(S_{len + 1, len + x}, S_{k \times x + 1, (k + 1) \times x}\) 重叠了一段区间且长度相同，那么 \(S_{len + 1, k \times x}\) 就可以作为一段新的伪循环节，且长度小于 \(x\)，那么 \(nxt_n\) 一样可以变大，矛盾。
首先需要了解下面这样一个性质：
给定两个正整数 \(p, q\) 如果一个长度不小于 \(p + q - \gcd(p, q)\) 的串 \(S\) 中存在长度为 \(p, q\) 的循环节，那么 \(\gcd(p, q)\) 也是 \(S\) 的循环节。
考虑将循环的意义用数学语言表达下来，不难发现对于 \(\forall i \in [1, n]\) 有 \(S_i = S_{i + p} = S_{i + q} = S_{i + px + qy}\)，根据裴蜀定理考虑到 \(px + qy = \gcd(p, q)\) 是一定有解的，那么就会有 \(S_i = S_{i + \gcd(p, q)}\) 也就意味着 \(\gcd(p, q)\) 也是一个循环节。
假设存在两个个长度为 \(p, q(\gcd(p, q) \ne p)\) 的循环节，\(p\) 为长度最小的循环节。那么显然有 \(\gcd(p, q) < p\)，根据上面的那条性质，\(\gcd(p, q)\) 也是一个循环节，那么最小循环节的长度就会是 \(\gcd(p, q)\) 而不是 \(p\)，矛盾。
