五、next数组细节理解
为什么按照next数组移动就可以保证不跳过匹配成功的字符串呢？
前面说过，如果匹配失败子串的首字符的位置会移动到匹配失败的位置，再向左移动next数组[i]格，匹配失败的那一位的next数组记录着前面字符的最大公共前后缀长度，由于前面的前缀都已经于主串匹配过了，只不过后缀后面的位置对不上，那么我们直接将后缀的起始位置对准匹配失败的位置，也就是向左移动next[i]个长度（也就是向左移动最大公共前后缀的长度），就能保证跳跃过程中没有错过任何可以匹配成功的串。还可以使主串中已经成功配对的后缀于子串的前缀相匹配，再向后匹配。
下图中，①=②=③=④，所以移动回去时保证前面的后缀会与匹配失误的地方对齐
上面展示的是有公共前后缀的情况，那么如果整个字符串都没有公共前后缀会怎么样？
- 将发挥KMP算法的最大作用！
我们只需大胆向后跳，不用再往前跳了
此动画后半部省略掉了，找到最后没有发现相同串
六、nextVal数组
讲完了next数组，接下来讲解nextval数组，nextVal数组是next数组的改进版，因为next数组还有改进的空间，那就是在生成数组的时候对在next数组的基础上，对失配字符的next数组下标进行读取，读取数组下标到字符串的下标位置，然后进行比较，如果不相等，那么不对其进行优化，如果读取失配讲完了next数组，接下来讲解nextval数组，nextVal数组是next数组的改进版，因为next数组还有改进的空间，那就是在生成数组的时候对在next数组的基础上，对失配字符的next数组下标进行读取，读取数组下标到字符串的下标位置，然后进行比较，如果不相等，那么不对其进行优化，如果读取失配
这样做的原理是什么呢？
如果此时a在与上面的字符串进行配对，那么a此时与b失配，说明对比的数是非a，按照next数组原理我们将下标为0的位置移动到上面b的位置，可是a已经和b对比过了，将下标为0的a移动过去必然也会失配，所有nextVal要先对失配的位置与next数组的值对应的下标的字符进行比较，相等就会读取其对应位置的next下标到失配位置的next下标。
七、KMP算法代码实现
讲完了原理，这里是代码实现。
- 可以将里面的next替换为nextVal，两者都为独立的数组生成函数。
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdlib.h> #include <assert.h> #include <stdio.h> void getNext(int * next,const char* s,int len) { assert(next && s); //判断两个指针是不是空指针 int i = 0, cur = -1; //i是当前位置、cur是当前最大相同前后缀的长度 next[0] = cur; while (i < len) { if (cur==-1||s[i]==s[cur]) //cur为-1的时候也要恢复成0同时i++ { next[i + 1] = cur+1; cur++; //cur恢复成0 i++; } else { cur = next[cur]; //如果失配，直接找到这个位置的next数组的值给到cur } } } int kmp(const char* p, const char* s) { int len = strlen(s); int* next = (int*)malloc(sizeof(len) * len); getNext(next, s, len - 1); assert(next); int i = 0, j = 0; //定义i为字符串下标，j为next数组下标 while (p[i]) { if (j==-1||p[i] == s[j]) //如果next数组下标为-1，next数组下标恢复为0，字符串下标+1 { i++; j++; if (s[j] == '\0') //如果字符串下标为‘\0’,查找成功返回i-j也就是字符串匹配成功位置的收个字符的下标 { free(next); next = NULL; return i - j; } } else { j = next[j]; //将此位置的next数组下标对准字符串对应位置得下标 } } free(next); next = NULL; return -1; //如果p[字符串下标]=='\0'，跳出循环，证明查找失败，返回-1 } int main() { char p[] = "abcdabecabcfdsafdasdasfdasfasdfasfdasafdsbc"; char s[] = "abecab"; printf("%d", kmp(p, s)); }
八、nextVal数组代码实现
void getNextVal(int *next,const char* s,int len) { assert(next); int i = 0, cur = -1; next[0] = cur; while(i < len) { if (cur == -1 || s[i] == s[cur]) //为-1注意处理 { i++; cur++; if (s[i] != s[cur]) //比next数组增加一个判断 { next[i] = cur; } else { next[i] = next[cur]; //如果相等，把next[cur]的值取过来 } } else { cur = next[cur]; } } }
完结
作者的话
KMP是一块硬骨头，建议各位能挑出一段长时间专门攻克它，不要今天看一点，明天再看一点，这样不会有收获，写代码不代表就已经真正理解了KMP，你最好要能熟练的讲给其他小伙伴KMP到底一种什么样的算法，记录一份详细的笔记，忘记的时候拿出来反复重温，最后如果觉得哪里没有理解，可以评论区留言或者私信作者，我会耐心地给大家来答疑解惑。当然如果有不足的地方还请各位帮忙补充。
