Algorithm - KMP
Created by : Mr Dk.
2021 / 03 / 13 23:51
Nanjing, Jiangsu, China
About
为了准备面试，逼自己看了之前一直都没看懂的 KMP 算法。现在大致看懂了思想，但是有一个小点还是没有懂。。。我好笨 😭
Knuth-Morris-Pratt (KMP) 字符串查找算法用于在一个主字符串 S 中查找一个模板串 W 出现的位置，由三位大神于 1977 年联合发表，并用三人的名字共同命名。其特性是能够在匹配期间确定下一个匹配可能开始的位置，从而避免重新检查之前匹配的字符。
Brute-Force
暴力匹配字符串法其实很简单。从主字符串开头开始，与模板串的开头比较。一旦遇到不匹配的字符，则从主字符串开始匹配位置的下一个位置起，与模板串开头重新比较。示意如下：
i
|
ABCDABCABCDABD
ABCDABD
|
j
两个字符串从开头开始匹配，匹配到第 7 个字符时失配。于是，下一轮匹配从如下位置开始：
i
|
ABCDABCABCDABD
ABCDABD
|
j
可以看到，i 和 j 指针都做了一次回溯。
KMP
KMP 算法的核心是，让 i 不回溯。在上面的例子中可以看到，ABCDAB 匹配成功，意味着前面的 AB 和后面的 AB 已经匹配成功了。那么下一次开始匹配时，可以直接从模板串的 AB 前缀之后一个位置开始匹配，如下图所示：
i
|
ABCDABCABCDABD
ABCDABD
|
j
i
|
ABCDABCABCDABD
ABCDABD
|
j
从上面的例子可以看到，i 指针没有动，而 j 指针往回滑了几个位置，但也没有滑动到 0。这里根本的原因是，之前匹配成功部分的模板串后缀，与模板串的前缀，有着长度为 2 的相同部分。所以，KMP 算法的核心是，找到模板串每个位置上的 最长公共前后缀长度。该长度如果确定，那么每次只需要将 j 指针向左滑动即可。滑动的具体距离为：之前匹配成功的子模板串长度，减去该串的最长公共前后缀长度。在上面的例子中，之前匹配成功的部分为 ABCDAB，最长公共前后缀为 AB，因此滑动距离为 6 - 2 = 4。
所以，想要进行模式匹配，就需要得到这个通常被称之为是 next[] 的数组。对模板串进行单独处理，得到了这个数组，那么就可以执行如下的算法：
int kmp_match(string haystack, string needle) {
int i = 0;
int j = 0;
while (i < (int) haystack.length() && j < (int) needle.length()) {
if (j == -1 || haystack[i] == needle[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == (int) needle.length()) {
return i - needle.length();
}
return -1;
}
其中，next[0] 的值一定为 -1，其含义为正好可以用如下的例子描述：
i
|
ABCDABCABBCDABDCDA
ABCDABD
|
j
当主字符串的字符与模板串的第一个字符也无法匹配时，j 指针将会被赋值为 -1 (next[0])，使得在下轮循环中 i 和 j 两个指针分别前进一步，i 指向了主字符串的下一个字符；j 正好也就重新指向了模板串的第一个字符。其含义为，当主字符串和模板串的第一个字符都无法匹配时，不得不强制去匹配主字符串的下一个字符。然而由于代码中 i 指针和 j 指针是同时前进的，所以先提前把 j 指针设置到 0 的前一个位置上去，这样指针前进后就恰好指向了模板串的第一个字符。
Next Array
这个数组的求法真的很让我痛苦。实际上，手写我是写得出的，放到代码里我就是想不通了。
简单的求法是，先写出模板串每个位置上的最长公共前后缀长度，然后将形成的数组右移一个位置，将最左边空出来的位置填上 -1 就是 KMP 使用的 next 数组了。next 数组的含义为，(当前位置的字符不算)，之前的子串中的最大公共前后缀长度；另外也可以理解为，如果在这个位置发生了失配，j 指针应该移动到的位置的下标，也就是模板串从头开始除去最长公共前缀后的第一个位置。
至于实现，并没有采用先得到最长公共前后缀长度再移位的做法，而是一步到位得到 next[]。但我暂时还是理解不了代码。
有一种解释是，可以将构造这个数组的过程也看成是匹配：模板串和它的每一个前缀子串的匹配。
vector<int> get_next_array(string needle) {
vector<int> next(needle.length(), -1);
int i = 0;
int j = -1;
while (i < (int) needle.length() - 1) {
if (j == -1 || needle[i] == needle[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;