KMP 算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。
在学习 KMP 算法之前，先来看看朴素的字符串匹配算法
1. 字符串匹配问题
字符串匹配问题是这样一个问题：给你一个字符串 S，再给你一个字符串 P （又称为模式串），需要你判断 P 是否在 S 中出现，在哪里出现。
最朴素的暴力做法就是将 P 作为一把“标尺”，不断的移动并进行比较，直到找到匹配的位置，如下图：
这种算法的优点十分明显，那就是简单，简单到小学生都会
缺点也很明显，效率低下，时间复杂度为 O(n * m)
光上面这个例子还不能引出 KMP 算法的核心思想，我们再来看一个例子
暴力算法依旧可以解决字符串匹配问题，但是从这个例子我们能发现更多细节
图中可以看到，字符串匹配在 p[5] 时失配，这时候我们还需要按照暴力算法，每次将 P 移动一位吗？
移动一位后，s[1] != p[0]，不匹配， 继续移动
直到从 s[3] 开始，s[3:5]（意思为下标在[3,5)的子串）= p[0:2]
这时候才刚好完成部分匹配，接下来才能开始继续比较后面的字符
如果你尝试了一步步移动模式串 P，你会发现你始终在将 S 的某一部分，与 P 的开头一部分进行比较。而这开头的一部分子串称为前缀，模式串 P 的前缀
那么 S 中我们比较的是哪一部分呢？
从过程而言，S 中比较的是任何一部分。但从结果而言，S 中需要比较的仅仅是末尾部分，也就是后缀
结合图片再来理解理解：
假设我们对主串 S 的匹配工作已经进行到了子串 s[i:j+1] 部分
这时候 s[j] 失配了，我们需要将模式串 P 向后移动
由于对 S 的遍历只到达了 j 的位置，所以对于 s[j] 之后的字符都是未知的，并且此时的目标是找到能让 s[j] 匹配的位置（如果存在的话）
随着模式串 P 的移动，会出现以下三种情况（下图任何长度等数据皆为示例）
- P 的前缀与
s[i:j]中的一部分匹配，而后面不匹配
- P 的前缀与
s[i:j]的后缀相匹配
s[i:j]无法找到合适的位置，P 从 j 开始重新匹配
情况 3 不用多说，是一种非常普遍的现象
情况 1 和情况 2 中，由于 j 往后的字符还没遍历，都处于未知状态，所以对于标尺 P 来说，最合适的位置就是它的一部分前缀已经匹配的位置。情况 1 显然不可能，虽然匹配了一部分前缀，但是后面的已知部分不匹配，所以这种情况可以跳过。我们真正需要找的位置是情况 2，也就是 s[i:j+1] 的后缀与 P 的前缀相同
知道了原理之后，怎么实现呢？如何跳过中间过程中 n 个情况 1，直接到达情况 2 ？
由于 s[i:j] 已经与 p[0:5] 匹配，所以“ s[i:j] 的后缀等于 P 的前缀”这句条件可以转化为，p[0:5] 中后缀等于前缀的部分，同时为了覆盖尽可能多的情况，也就是标尺移动的尽量要少，所以取最长的相等长度
使用通用的语言表达：
当 P 失配时，我们要在 P 的已匹配部分中找到 后缀等于前缀 的最大子串长度，并将 P 移动到相应位置继续进行匹配
例如 P 为 ABCABD 当第六个字符失配时，前五个字符 ABCAB 是匹配的，这时候后缀等于前缀的最大长度为 2 （”AB”）
2. next 数组
next 数组是对于模式串 P 而言的，next[i] 表示 P[0] ~ P[i] 这个子串中 前k个字符 与 后k个字符 相等的最大的 k。同时由于数组下标从 0 开始，所以 next[i] 又可以表示为失配后跳转到的下一个下标，从这个位置继续开始匹配。
对于上图中的 next 数组该如何构建呢？
显然，对于第二次出现的 A 或 B，由于P[i] == P[next[i - 1]]，所以 next[i] = next[i - 1] + 1
当然，这只适用于部分情况，而更多普遍的情况需要更复杂的算法
我们需要比较的是前缀与后缀，所以需要两个指针，now 与 x
图中 next[x] 该是多少呢，反正不可能是 6，难道是 0 吗？
你应该也看出来了，前缀 “ABC” 与后缀 “ABC” 相同，所以 next[x] = 3
从算法的角度来看，虽然 P[now] != P[x] ，但是他们前面的部分是相同的，也就是图中的绿色部分，我们将绿色部分单独看成一个模式串，而 P[0:now]部分的 next 数组已经处理好了，所以绿色部分我们可以很容易找到最大长度的 k，也就是 next[now - 1]。
所以我们从 next[now - 1]的位置继续匹配，发现 P[x] = P[next[now - 1]]，所以 next[x] = next[now - 1] + 1
如果他俩不相等，那么我们继续这样划分子串，直到相等或者下标为0
下面贴上代码
int next[n];
void buildNext() {
int now = 0, x = 1;
while (x < n) {
if (p[now] == p[x]) {
next[x] = next[now] + 1;
now++;
x++;
} else if (now > 0) {
now = next[now - 1];
} else {
next[x] = 0;
x++;
}
}
}3. 实际应用
贴一个简单的字符串匹配代码
string s, p;
// 省略输入部分
int next[p.size()];
// 省略next数组构造
int tar = 0; // 主串中匹配的位置
int pos = 0; // 模式串中匹配的位置
while (tar < s.size()) { // 查找s中所有匹配的位置
if (s[tar] == p[pos]) {
tar++;
pos++;
} else if (pos > 0) {
pos = next[pos - 1];
} else {
tar++;
}
if (pos == p.size()) { // 匹配成功
cout << tar - pos + 1 << endl; // 输出匹配的起始位置
pos = next[pos - 1]; // 移动标尺，继续寻找下个匹配
}
}