KMP 字符串匹配算法
暴力算法低效在哪？
字符串匹配如果使用暴力写法的话，我们需要不断移动匹配字符串的位置，同时一一对比此时字符串是否相同。这个过程中有没有浪费时间呢？答案是肯定的。
首先我们需要知道，对于每次匹配时，我们已经知道出现未匹配字符串之前的各个字符的内容了，我们能不能考虑利用我们已匹配的的字符来优化我们的匹配流程呢？
首先，我们先了解前缀后缀这两个概念。对于 abc 来说，前缀是 ['a', 'ab'] ，后缀是 ['c', 'bc'] 。那这个怎么用呢？
next 数组
next 数组保存了匹配字符串的前 n 个字符组成的字符串的最长相同前缀和后缀的长度。
使用方法：我们下次移动不再 1 个步长地移动了，我们移动 x 个步长，x 怎么算呢？
移动步长 x = 已匹配的字符数 - 对应的 next 值
例如：BBCXABCDABVABCYUIYNDUYV 匹配 ABCDABD ，当前匹配字符串在下标为 4 的位置，同时此时 next 数组为 [0, 0, 0, 0, 1, 2, 0] ，我们当前移动步长应为 6-2，即 4 位。也就是说将匹配字符串移动到已匹配字符前缀后缀相同的最前的位置，而且我们还可以直接从未成功匹配的位置开始匹配。此时即可实现利用已匹配字符。
好了，我们已经知道 KMP 算法的精髓是 next 数组，那么我们怎么求 next 数组呢？
转换一下思维，既然是求前缀后缀相同的最大长度，我们可以用匹配字符串和自己比较（当然从 0 开始是没有意义的）。我们用 s1 来匹配 s2，移动 s1 来匹配不同下标开始的 s2，在某一个下标下匹配时，都有一个 s1 的移动指针 m，当前 m 位置匹配时，s2 的 next 的值就是它前一位置的 next 值加一，即当前匹配长度，如果当前 m 位置不匹配怎么办呢？我们可以看到已匹配的 s1 子串在 s2 中已经求出了 next 的值，因此我们可以直接移动 s1 到已匹配字串的后缀和前缀相同的位置继续求 next 的值。
代码
class Solution {
private:
vector<int> preprocess(string& s) {
vector<int> kmp(s.length());
int i = 1, m = 0;
kmp[0] = 0;
while (i < s.length()) {
if (s[i] == s[m]) {
kmp[i++] = ++m;
} else if (m > 0) {
m = kmp[m - 1];
} else {
kmp[i++] = 0;
}
}
return kmp;
}
public:
int strStr(string haystack, string needle) {
if (needle.length() == 0) return 0;
vector<int> kmp = preprocess(needle);
for (int i = 0, j = 0; i < haystack.length();) {
if (needle[j] == haystack[i]) { ++i; ++j; }
if (j == needle.length()) return i - j;
if (i < haystack.length() && needle[j] != haystack[i]) {
if (j > 0) j = kmp[j - 1];
else ++i;
}
}
return -1;
}
};