第78篇 C++实现字符串匹配（三）KMP算法
- 1.KMP算法简单描述
- 2.自解next
- 3.原next
- 4.改进next
- 5.KMP代码
- 5.1.原KMP
- 5.2.改进KMP
- 6.所有代码
- 7.结语
1.KMP算法简单描述
（建议使用电脑阅读）
首先上大佬的链接
数据结构KMP算法配图详解（超详细）
虽然别人写得很好，但是我还是想尝试一下自己能理解多少，所以写一写自己的看法，看看自己能不能把这个算法表述得明白。
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。（百度百科）
以前上数据结构的时候，我有研究过，但是不明不白的，而且当时我没有注意到书中有没有大佬提到的一个词（字符串的最长相等前后缀）（也许书上有也许没有），知道了这个词之后，就能好理解很多了，因为这是求解next值的关键，即回溯问题的关键所在。
那么如何判断一个字符串是否有最长相等前后缀呢？
首先前后缀的长度不能等于字符串的总长度。
（1）字符串长度大于1，有最长相等前后缀
如字符串：abcdab（大佬的例子）
前缀的集合：{a,ab,abc,abcd,abcda}
后缀的集合：{b,ab,dab,cdab,bcdab}
那么最长相等前后缀就是ab，最长相等前后缀长度为2
（2）字符串长度大于1，没有最长相等前后缀
如字符串：abcdef
前缀的集合：{a,ab,abc,abcd,abcde}
后缀的集合：{f,ef,def,cdef,bcdef}
没有最长相等前后缀，最长相等前后缀长度为0
（3）字符串长度等于1，没有最长相等前后缀
这个很好理解，前后缀的长度不能等于字符串的总长度，最长相等前后缀长度为0
最长相等前后缀是解决next值的关键，那么二者是如何关联的呢？
首先看一下有关回溯的问题
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | c | a | b | a | b | c | a | b | n | c |
| T | a | b | c | a | b | n |
由表可以看出，当比到S[5]和T[5]时，两者是不匹配的，那么这时我们希望T回溯到哪里呢？
回溯到T[2]，为什么？因为S[0]==S[3],S[2]==S[2],S[1]==S[4],且T[0]==T[3],T[2]==T[2],T[1]==T[4]，已经没有必要再去进行比较，直接拿过来就行了。然后用T[2]和S[5]比，不行再回溯。
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | c | a | b | a | b | c | a | b | n | c |
| T | a | b | c | a | b | n |
举这个例子不是要看一次完全的匹配过程，而是要看的是最长相等前后缀。当我们匹配到n时，n和主串的a是不匹配的，而此时我们需要回溯，那么为什么回溯到子串2的位置呢？注意看n前面的字符串abcab，它的最长相等前后缀是什么？没错是ab，长度是2。这个2和位置2有什么关系吗？这就是联系所在了，当子串T的字符T[j]与主串某字符不匹配时，我们需要将子串T的位置回溯到字符T[j]前面字符串str[0…j-1]的最长相等前后缀的长度处，为什么是长度呢？因为长度刚好是最长相等前后缀的下一个字符，比如以上2刚好是ab后面的c的位置。这里我们大概可以了解KMP匹配的原理了吧，虽然我的表述不好（哈哈，太勉强）。
然后再看next数组中值的求解公式。
![求next[j]](https://img-blog.csdnimg.cn/d57c5b1c4fb44073bc466e5b456d4a82.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAYnVnX-WQmw==,size_20,color_FFFFFF,t_70,g_se,x_16)
上面我们已经知道，next[j]的值是字符串str[0…j-1]最长相等前后缀的长度，则对于目标字符串target的next求解：
（1）如果j 等于0，那么next[j] 等于 -1，这是众所周知的初始条件，就是不管是什么串，第一个next值next[0]肯定是-1，为什么这样呢？这是因为target[0]前面没有字符，就没这个和最长相等前后缀的这个概念说法。而且还可以确定next[1]等于0，因为当j等于1时，str[0…1-1]也就是str[0…0]，相当于只有一个字符串，也就是说target[1]前面只有一个字符，不存在最长相等前后缀，最长相等前后缀的长度是0。
（2）对于j>=2开始，就有可能存在最长相等前后缀了，所以我们得求解，也就是公式第一个条件的求解方式。至于代码实现，可以先看如何暴力求解next。aaaaaaa
2.自解next
重要的话说n遍：next[j]的值是字符串str[0…j-1]最长相等前后缀的长度
对于字符串target，如果target[j]前面的字符str[0…j-1]为给定字符串：abcdab，如何暴力求解str[0…j-1]最长相等前后缀呢？即如何暴力求解一个字符串的最长相等前后缀呢？
| 串 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b |
最长？那么我们先匹配最长的前后缀就行了，如果最长前后缀不相等，那么就减掉一个长度，直到出现相等前后缀或者长度为0为止。
如上字符串：abcdab
前缀的集合：{a,ab,abc,abcd,abcda}
后缀的集合：{b,ab,dab,cdab,bcdab}
（1）先匹配最长的，当前长度为5，f：abcda，e：bcdab，第一个字符就不相等，长度减一，长度为4；
（2）当前长度为4，f：abcd，e：cdab，第一个字符就不相等，长度减一，长度为3；
（3）当前长度为3，f：abc，e：dab，第一个字符就不相等，长度减一，长度为2；
（4）当前长度为2，f：ab，e：ab，第一个字符相等，判断第二个字符，第二个字符也相等，即找到最长相等前后缀。
我觉得这样应该够简洁了吧，然后我们用代码实现的时候，并不需要把字符串截取出来，而是通过下标匹配就行了，为什么呢？可以看到，（1）时，f是从0开始，而e是从1开始；（2）时，f是从0，开始，而e是从2开始；（3）时，f是从0开始，e是从3开始；（4）时，f从0开始，而e是从4开始的。如此就可以发现，最长相等前后缀的长度k初始为0，我们先从m = 0(f的起始位置)，n = 1（e的起始位置）开始，如果f[m] == e[n]，则m++，n++，k++，否则m = 0，n++，k = 0（n一直往后走，m和k回溯），如此反复；
代码如下：
void myGetNext(string target,int *next) {
int j = 1;//我们已经知道next[0]的值，所以直接从j = 1开始求解
int k = -1;//next[0] = -1
next[0] = -1;//next[0] = -1
int tlen = target.size();//目标（模式）串的长度
string front = "";//字符串str[0...j-1]即target[i]前面的字符串
front += target[0];//j==1时，j前面的字符串只有一个字符，即target[0]
while(j < tlen) {//循环条件不用说吧
int flen = front.size();//计算target[j]前面字符串str[0...j-1]的长度
k = 0;//k初始为0
/*这一段的解释：
m = 0,m是front的起始位置*/
int m = 0;//f的起始位置
int n = 1;//e的起始位置
while(m < n && n < flen) {
if(front[m] == front[n]) {
k++;//相等三者都++
n++;
m++;
}
else {
m = 0;//不相等n++，m和k回溯
n++;
k = 0;
}
}
next[j] = k;//计算完毕，next[j]等于k
front += target[j];//相当于为后一个字符做准备，后一个字符是target[j+1]，所以它的front是str[0...j]
j++;
}
}
如果KMP的next求解写成这样就很容易理解了，当然事实不是这样的了，因为有更简洁的代码，更神奇清奇的思路，而且求解过程还有回溯，我就不太反应过来，自己思索了很久后，就按自己的想法写下了这一篇暴力求解，所以这个只是辅助理解理解，既然有更好的为什么不要。
3.原next
重要的话说n遍：next[j]的值是字符串str[0…j-1]最长相等前后缀的长度
对于字符串target，如果target[j]前面的字符str[0…j-1]为给定字符串：abcdab，原next求解方式如何求解str[0…j-1]最长相等前后缀呢？即原next求解方式如何求解一个字符串的最长相等前后缀呢？
| 串 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b |
当然不能用暴力的思想，从最长开始求解，这里得从最短求解了。要求str[0…j-1]的最长相等前后缀，我们不能只看它一个整体，而是要看它前面的str[0…0]，str[0…1]，str[0…2]、、、str[0…j-2]的所有情况，所以我们不能只针对一个给定的字符串，我们还要从头开始。
比如给定的target是:abcdabc
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
（1）首先我们确定如下结果，即初始条件j = 0，k = -1
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
| next | -1 | ? | ? | ? | ? | ? | ? |
（2）next[1]的值是很好确定的，判断条件 k == -1 ||target[j] == target[k]，因为k == -1，即taregt[1]前面只有一个字符，没有别的字符和它比较，所以没有最长相等前后缀，即最长相等前后缀的值就是k++后的值，就是0.当然为了避免target[j] 和 target[k]比较，使用 == 符号短路，而且我们发现j是从0开始的，就说明，我们每一次的判断操作，都是在target[j + 1]字符前面的字符串上操作。
（3）如何确定next[2]呢，这个很好理解，因为target[2]前面只有两个字符，target[0]和target[1]，直接比较他们是否相等就可以了，而相等那么target[2]前面的字符串最长相等前后缀长度就是1，如果不相等那就是0，而这里是不相等，所以答案是0，且看此时j为1（不是2），k是0，我们的判断是target[j]==target[k]（即target[1]==target[0]），不相等是吧，进行k回溯，k = next[k]（即k = next[0] = -1），k又回到-1，则执行k++（k又为0）,j++（j是1，j++变成2），所以得next[2] = 0；
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
| next | -1 | 0 | 0 | ? | ? | ? | ? |
（4）next[3]的结果有三种情况，0,1,2三种，此时j为2，k为0，那么为什么我们可以直接比较target[2]和target[0]（即target[j]和target[k]），而不是像暴力法求解一样先比较target[0]和target[1]呢，幂幂之中自有定数，这就是原next解法的妙处，为什么？因为我们在上一步已经知道target[0]和target[1]是不相等的，所以就没有再比较的必要了，注意在上一步已经知道target[0]和target[1]是不相等，因为我们确确实实在上一步比较过它们。所以按照暴力法的思想，我们是不是只需要比较target[2]和target[0]就可以了？对，没错。而target[2]和target[0]也不相等，所以k = next[k]（即k = next[0] = -1），k又回到了-1，则执行k++（k又为0）,j++（j是2，j++变成3），所以得next[3] = 0；
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
| next | -1 | 0 | 0 | 0 | ? | ? | ? |
（5）next[4]的结果有四种情况，0,1,2，3四种，此时j为3，k为0，直接比较target[3]和target[0]（即target[j]和target[k]），不用多说了吧，因为我们在上一步已经知道target[0]和target[1]是不相等的，且知道target[0]和target[2]是不相等的，所以就没有再比较的必要了，注意在上一步已经知道target[0]和target[1]是不相等，target[0]和target[2]也是不相等的，因为我们确确实实在上一步比较过它们。所以按照暴力法的思想，我们是不是只需要比较target[3]和target[0]就可以了？而target[3]和target[0]也不相等，所以k = next[k]（即k = next[0] = -1），k又回到了-1，则执行k++（k又为0）,j++（j是3，j++变成4），所以得next[4] = 0；
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
| next | -1 | 0 | 0 | 0 | 0 | ? | ? |
（6）next[5]的结果有五种情况，0,1,2，3，4五种，此时j为4，k为0，直接比较target[4]和target[0]（即target[j]和target[k]），不用多说了吧，因为我们在上一步已经知道target[0]和target[1]是不相等的，且知道target[0]和target[2]是不相等的，target[0]和target[3]也是不相等的，所以就没有再比较的必要了，注意在上一步已经知道target[0]和target[1]是不相等，target[0]和target[2]也是不相等的，target[0]和target[3]也是不相等的，因为我们确确实实在上一步比较过它们。所以按照暴力法的思想，我们是不是只需要比较target[4]和target[0]就可以了？而target[4]和target[0]相等了是吧（终于有一个相等了），所以执行k++（k为0，k++变成1）,j++（j是4，j++变成5），所以得next[5] = 1；
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
| next | -1 | 0 | 0 | 0 | 0 | 1 | ? |
（7）最后一个了，next[6]的结果有六种情况，0,1,2，3，4,5六种，此时j为5，k为1，直接比较target[5]和target[1]（即target[j]和target[k]），不用多说了吧，因为我们在上一步已经知道target[0]和target[1]是不相等的，且知道target[0]和target[2]是不相等的，target[0]和target[3]也是不相等的，而target[4]和target[0]相等，这说明什么，说明第一种情况长度为5时第一个字符就不匹配，第二种情况长度为4时第一个字符就不匹配，第三种情况长度为3时第一个字符就不匹配，而第四种情况长度为2时，第一个字符匹配了，因此，如果第二个字符再匹配，那么就可以得出最长相等前后缀的长度就是2了，注意在上一步已经知道target[0]和target[1]是不相等，target[0]和target[2]也是不相等的，target[0]和target[3]也是不相等的，target[4]和target[0]相等，因为我们确确实实在上一步比较过它们。所以按照暴力法的思想，我们是不是只需要比较target[5]和target[1]就可以了？而target[5]和target[1]相等了是吧，所以执行k++（k为1，k++变成2）,j++（j是5，j++变成6），所以得next[6] = 2；
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | b | c | d | a | b | c |
| next | -1 | 0 | 0 | 0 | 0 | 1 | 2 |
（8）求解结束。但是上面这种情况并不是很好的体现回溯问题，我们可以假定以下把字符串换成如下情况，然后再求解next[6]：
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | f | c | d | a | b | c |
| next | -1 | 0 | 0 | 0 | 0 | 1 | ? |
这个情况下前（1）到（6）步都是满足的，具体说一说第（7）步的不同之处。
next[6]的结果有六种情况，0,1,2，3，4,5六种，此时j为5，k为1，直接比较target[5]和target[1]（即target[j]和target[k]），不用多说了吧，因为我们在上一步已经知道target[0]和target[1]是不相等的，且知道target[0]和target[2]是不相等的，target[0]和target[3]也是不相等的，而target[4]和target[0]相等，这说明什么，说明第一种情况长度为5时第一个字符就不匹配，第二种情况长度为4时第一个字符就不匹配，第三种情况长度为3时第一个字符就不匹配，而第四种情况长度为2时，第一个字符匹配了，因此，如果第二个字符再匹配，那么就可以得出最长相等前后缀的长度就是2了，注意在上一步已经知道target[0]和target[1]是不相等，target[0]和target[2]也是不相等的，target[0]和target[3]也是不相等的，target[4]和target[0]相等，因为我们确确实实在上一步比较过它们。所以按照暴力法的思想，我们是不是只需要比较target[5]和target[1]就可以了？而target[5]和target[1]不相等了是吧，说明第四种情况长度为2不匹配了，求第五种情况长度为1时，是否匹配，所以执行k = next[k]（即k = next[1] = 0），即比较target[5]和target[0]，如果target[5]和target[0]相等，就可以得出最长相等前后缀的长度就是1了，但是此时target[5]和target[0]不相等，所以第五种情况长度为1时也不匹配，所以只能是最后一种，长度 为0，k = next[k] （k = next[0] = -1），k又回到了-1，则执行k++（k又为0）,j++（j是5，j++变成6），所以得next[6] = 0；
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| target | a | f | c | d | a | b | c |
| next | -1 | 0 | 0 | 0 | 0 | 1 | 0 |
已经够清楚了吧（哈哈，反正我觉得清楚了）。就是说我们在求解的过程中，后面要做的某些事我们在前面已经做好了，不需要重复做了，比如两个比较过的值，我们已经知道比较结果，不需要再重复去比较了，我们只需比较没有比较过的，就可以了。看完上面，应该大概的明白k = next[k]是什么意思了吧。（最好自己写一遍，才能更好地理解）
代码众所周知：
void getNext(string target,int *next) {
int j = 0;
int k = -1;
next[0] = -1;
int tlen = target.size();
while(j < tlen) {
if(k == -1 || target[j] == target[k]) {
j++;
k++;
next[j] = k;
}
else {
k = next[k];
}
}
}
4.改进next
然而还没有结束。大佬的话：为什么KMP算法这么强大了还需要改进呢？
大佬的例子：
主串s=“aaaaabaaaaac”
子串t=“aaaaac”
| 串 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | a | a | a | a | b | a | a | a | a | a | c |
| T | a | a | a | a | a | c |
按照next的求解方法，这个例子中当‘b’与‘c’不匹配（即S[5]和T[5]不匹配）时，应该‘b’与’c’前一位的‘a’比,即T回溯到4（字符‘c’前面的最长相等前后缀长度是4）：
（1）匹配S[5]与T[4]，这显然是不匹配的，T回溯到3；
（2）然后匹配S[5]与T[3]，这显然也不匹配的，T回溯到2；
（3）然后是匹配S[5]与T[2]，这显然也不匹配，T回溯到1；
（4）然后是匹配S[5]与T[1]，这显然也不匹配，T回溯到0；
（5）然后是匹配S[5]与T[0]，这显然也不匹配的，，T回溯到-1；
（6）因为此时回溯后j是-1，所以执行j++，i++，即j回到模式串的首位，而主串后移一位，依次判断直到结束为止。
由此我们可以知道，以上几步全做的是无用功，所以我们知道没有必要再将‘b’与‘a’比对了，因为回溯后的字符和原字符是相同的，原字符不匹配，回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。
我们改进后的next数组命名为：nextval数组。KMP算法的改进可以简述为：如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。
如字符串"ababaaab"的next数组以及nextval数组分别为：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| next | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 |
| nextval | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 |
这里有一个迷惑的点就是，既然是如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。 ，那么求解nextval值的过程中，应该与next值有关啊，那就说明我们先求next值，再去求nextval的值，那为啥代码是直接求nextval呢？
这一点其实很好理解，因为我们的代码就是在求解next值的代码上做一些手脚而已，只是添加了一个小小的判断，如果不加判断，它还是求解next值的函数。
对于如下字符串，再写一次求解过程：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
（1）确定已知条件，j为0，k为-1，nextval[0] = -1
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | ? | ? | ? | ? | ? | ? | ? |
（2）此时j为0，k为-1，按照求next的步骤，next[j] = k是吧，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，即找到了满足(k == -1 || target[j] == target[k])的k再加一，j++，next[j ] = k，但是求nextval的话，此时我们先要判断target[j] 是否等于 target[k]，如果不等，那么nextval[j ] = k = next[j]，如果相等，则nextval[j] = nextval[k] = next[k]；显然target[1] 不等于 target[0]，所以nextval[0] = k = next[j] = 0；
（3）此时j为1，k为0，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，显然回溯到k == -1，执行k++，j++，显然target[2] 等于 target[0]，所以nextval[2] =nextval[0] = -1；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | 0 | -1 | ? | ? | ? | ? | ? |
（3）此时j为2，k为0，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，显然不需要回溯，因为target[2] == target[0]，执行k++，j++，显然target[3] 等于 target[1]，所以nextval[3] =nextval[1] = 0；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | 0 | -1 | 0 | ? | ? | ? | ? |
（4）此时j为3，k为1，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，显然不需要回溯，因为target[3] == target[1]，执行k++，j++，显然target[4] 等于 target[2]，所以nextval[4] =nextval[2] = -1；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | 0 | -1 | 0 | -1 | ? | ? | ? |
（5）此时j为4，k为2，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，显然不需要回溯，因为target[4] == target[2]，执行k++，j++，显然target[5]不 等于 target[3]，所以nextval[5] =next[5] = k = 3；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | 0 | -1 | 0 | -1 | 3 | ? | ? |
（6）此时j为5，k为3，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，显然回溯到k = 0（target[5]和target[3]不等，target[5]和target[0]相等），执行k++，j++，显然target[6] 不等于 target[1]，所以nextval[6] =next[6] = 1；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | 0 | -1 | 0 | -1 | 3 | 1 | ? |
（7）此时j为6，k为1，当k回溯到已经满足这个条件(k == -1 || target[j] == target[k])的时候，说明已经找到了next[j]的值，显然回溯到k = 0（target[6]和target[1]不等，target[6]和target[0]相等），执行k++，j++，显然target[7] 等于 target[1]，所以nextval[7] =nextval[1] = 0；
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| nextval | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 |
代码分析：
void getNextValue(string target,int *nextValue) {
int j = 0;
int k = -1;
nextValue[0] = -1;
int tlen = target.size();
while(j < tlen)
{
if (k == -1 || target[j] == target[k])
{
j++;
k++;
if (target[j] != target[k]) {
nextValue[j] = k;
}
else {
nextValue[j] = nextValue[k];
}
}
else {
k = nextValue[k];
}
}
}
过程有了，代码也有了，但是似乎还不是说明为什么要这么做的原因吧？为什么要这么做？
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| target | a | b | a | b | a | a | a | b |
| next | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 |
| nextval | -1 | 0 | -1 | 0 | -1 | 3 | 1 | 0 |
且看这个字符串在主串的匹配过程中，匹配不成功的情况：
（1）j = 0，target[0]匹配不成功的时候，j回溯到-1，则执行i++，j++，即主串往后移，这个应该不用说明吧。
（2）j = 1，target[1]匹配不成功，那么回溯到第一个即target[0]来匹配，这个也很浅显。
（3）j = 2，target[2]匹配不成功，那么按照next的值，我们回溯到j = 0,处比较，但是，j = 0和j = 2处的字符相同啊，没有必要再比较吧？所以按nextval直接取-1，主串后移。
（4）j = 3，target[3]匹配不成功，按照next的值，我们回溯到j = 1,处比较，但是，j = 1和j = 3处的字符相同啊，没有必要再比较吧？所以按nextval直接取0，因为target[3]和target[0]是不一样的。为什么知道肯定不一样？因为我们在求next或者nextval的时候比过了。
（5）j = 4，target[4]匹配不成功，按照next的值，我们回溯到j = 2,处比较，但是，j = 2和j = 4处的字符相同啊，回溯到0处，j = 0和j = 4处的字符也相同，没有必要再比较吧？所以按nextval直接取-1，主串后移。
（6）j = 5，target[5]匹配不成功，按照next的值，我们回溯到j = 3,处比较，因为target[5]和target[3]是不一样的，所以有必要比较。
（7）j = 6，target[6]匹配不成功，我们知道，target[5]和target[6]是相等的，target[5]和target[0]是相等的，所以，我们可以回溯到j = 1处，因为target[6]和target[1]是不相等的。
（8）j = 7，target[7]匹配不成功，那么回溯到第一个即target[0]来匹配，这个也很浅显，因为target[0]和target[7]不相等。
以上就是这个字符串匹配不成功的所有情况，看了应该能明白一点为什么改进了吧。
5.KMP代码
众所周知的代码：
5.1.原KMP
//KMP算法
int knuthMorrisPratt(string mainString,string target) {
int mlen = mainString.size();
int tlen = target.size();
int* next = new int[tlen];
getNext(target, nextValue);
int i = 0;
int j = 0;
while(i < mlen && j < tlen) {
if (j == -1 || mainString[i] == target[j]) {
i++;
j++;
}
else {
j = next[j];
}
}
if (j >= tlen) {
return i - tlen;
}
return -1;
}
void getNext(string target,int *next) {
int j = 0;
int k = -1;
next[0] = -1;
int tlen = target.size();
while(j < tlen) {
if(k == -1 || target[j] == target[k]) {
j++;
k++;
next[j] = k;
}
else {
k = next[k];
}
}
}
5.2.改进KMP
//KMP算法
int knuthMorrisPratt(string mainString,string target) {
int mlen = mainString.size();
int tlen = target.size();
int* nextValue = new int[tlen];
getNextValue(target, nextValue);
int i = 0;
int j = 0;
while(i < mlen && j < tlen) {
if (j == -1 || mainString[i] == target[j]) {
i++;
j++;
}
else {
j = nextValue[j];
}
}
if (j >= tlen) {
return i - tlen;
}
return -1;
}
void getNextValue(string target,int *nextValue) {
int j = 0;
int k = -1;
nextValue[0] = -1;
int tlen = target.size();
while(j < tlen)
{
if (k == -1 || target[j] == target[k])
{
j++;
k++;
if (target[j] != target[k]) {
nextValue[j] = k;
}
else {
nextValue[j] = nextValue[k];
}
}
else {
k = nextValue[k];
}
}
}
6.所有代码
这是我的所有代码，加了测试的，为了验证我的getNext，我也加了测试函数，可以帮我看看有没有什么错误，如有错误，请以斧正。
#include <iostream>
using namespace std;
#include <string>
//Knuth Morris Pratt KMP算法
int knuthMorrisPratt(string mainString,string target);
void getNextValue(string target,int *nextValue);
void knuthMorrisPrattTest();
void getNext(string target,int *next);
void getNextTest();
void myGetNext(string target,int *next);
void myGetNextTest();
int main() {
knuthMorrisPrattTest();
myGetNextTest();
getNextTest();
return 0;
}
//KMP算法
int knuthMorrisPratt(string mainString,string target) {
int mlen = mainString.size();
int tlen = target.size();
int* nextValue = new int[tlen];
getNextValue(target, nextValue);
int i = 0;
int j = 0;
while(i < mlen && j < tlen) {
if (j == -1 || mainString[i] == target[j]) {
i++;
j++;
}
else {
j = nextValue[j];
}
}
if (j >= tlen) {
return i - tlen;
}
return -1;
}
void getNextValue(string target,int *nextValue) {
int j = 0;
int k = -1;
nextValue[0] = -1;
int tlen = target.size();
while(j < tlen)
{
if (k == -1 || target[j] == target[k])
{
j++;
k++;
if (target[j] != target[k]) {
nextValue[j] = k;
}
else {
nextValue[j] = nextValue[k];
}
}
else {
k = nextValue[k];
}
}
}
void knuthMorrisPrattTest() {
string mainString;
string target;
int contin = 1;
do {
system("cls");
cout << "当前检测的是KMP算法\n" << endl;
cout << "请输入mainString：";
cin >> mainString;
cout << "请输入target：";
cin >> target;
int result = knuthMorrisPratt(mainString, target);
if(result != -1) {
cout << target << "的起始位置在" << mainString << "的" << result << "处" << endl;
}
else {
cout << target << "不在" << mainString << "中" << endl;
}
cout << "继续检测输入1，否则输入0：";
cin >> contin;
} while (contin == 1);
cout << "欢迎再次检测！" << endl;
}
void getNext(string target,int *next) {
int j = 0;
int k = -1;
next[0] = -1;
int tlen = target.size();
while(j < tlen) {
if(k == -1 || target[j] == target[k]) {
j++;
k++;
next[j] = k;
}
else {
k = next[k];
}
}
}
void getNextTest() {
int contin = 1;
do {
system("cls");
cout << "这是测试getNext()" << endl;
string target = "";
cout << "请输入target：";
cin >> target;
int tlen = target.size();
int* next = new int[tlen];
getNext(target, next);
cout << "target：[";
for(int i = 0;i < tlen - 1;i++) {
cout << target[i] << " ";
}
cout << target[tlen - 1] << "]" << endl;
cout << "next：[";
for(int i = 0;i < tlen - 1;i++) {
cout << next[i] << " ";
}
cout << next[tlen - 1] << "]" << endl;
cout << "继续检测输入1，否则输入0：";
cin >> contin;
} while(contin == 1);
cout << "欢迎再次检测！" << endl;
}
void myGetNext(string target,int *next) {
int j = 1;
int k = -1;
next[0] = -1;
int tlen = target.size();
string front = "";
front += target[0];
while(j < tlen) {
int flen = front.size();
k = 0;
int m = 0;
int n = 1;
while(m < n && n < flen) {
if(front[m] == front[n]) {
k++;
n++;
m++;
}
else {
m = 0;
n++;
k = 0;
}
}
next[j] = k;
front += target[j];
j++;
}
}
void myGetNextTest() {
int contin = 1;
do {
system("cls");
cout << "这是测试myGetNext()" << endl;
string target = "";
cout << "请输入target：";
cin >> target;
int tlen = target.size();
int* next = new int[tlen];
myGetNext(target, next);
cout << "target：[";
for(int i = 0;i < tlen - 1;i++) {
cout << target[i] << " ";
}
cout << target[tlen - 1] << "]" << endl;
cout << "next：[";
for(int i = 0;i < tlen - 1;i++) {
cout << next[i] << " ";
}
cout << next[tlen - 1] << "]" << endl;
cout << "继续检测输入1，否则输入0：";
cin >> contin;
} while(contin == 1);
cout << "欢迎再次检测！" << endl;
}
7.结语
写了一天了，大佬的文章前几天看的，看了七八遍吧，反正好几遍，看到最长相等前后缀的时候我就有了点头绪，然后再慢慢琢磨，慢慢自己写代码，慢慢理解他的文章，然后写了这一篇文章，也许很不到位，但能够证明这个时间段我对这个算法的理解程度是怎么样的。
越难的东西越花时间，前两个算法BF和RK看一眼就懂了，但是这个KMP看了好几遍才有头绪，要有耐心，而且要动手写一写，光看是不怎么行的，要写，写代码才是正道，写了就算不明白它的原理是什么，要用的时候也许有记忆就写出来了（哈哈），当然写了一遍大概就能好了。
记住要写（记得点赞加关注，哈哈）。
