学习kmp知识点顺序
1、字符串前缀和后缀的概念
如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：
）：
2、kmp算法
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。变成：向右移动4位后，S[10]跟P[2]继续匹配。为什么要向右移动4位呢，因为移动4位后，模式串中又有个“AB”可以继续跟S[8]S[9]对应着，从而不用让i 回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀，然后根据前缀后缀求出next 数组，最后基于next 数组进行匹配。
3、next数组的理解
换言之，对于给定的模式串：ABCDABD，它的最大长度表及next 数组分别如下：
根据最大长度表求出了next 数组后，从而有
失配时，模式串向右移动的位数为：失配字符所在位置- 失配字符对应的next 值
而后，你会发现，无论是基于《最大长度表》的匹配，还是基于next 数组的匹配，两者得出来的向右移动的位数是一样的。为什么呢？因为：
根据《最大长度表》，失配时，模式串向右移动的位数 = 已经匹配的字符数 – 失配字符的上一位字符的最大长度值而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 – 失配字符对应的next 值其中，从0开始计数时，失配字符的位置 = 已经匹配的字符数（失配字符不计数），而失配字符对应的next 值 =失配字符的上一位字符的最大长度值，两相比较，结果必然完全一致。
所以，你可以把《最大长度表》看做是next 数组的雏形，甚至就把它当做next 数组也是可以的，区别不过是怎么用的问题。
4、通过递归计算next数组
如果对于值k，已有p0 p1, …, pk-1 = pj-k pj-k+1, …, pj-1，相当于next[j] = k。相当于模式串向右移动j – next[j] 位。
假定给定模式串ABCDABCE，且已知next [j] = k（相当于“p0 pk-1” = “pj-k pj-1” = AB，可以看出k为2），现要求next [j + 1]等于多少？因为pk = pj = C，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）。代表字符E前的模式串中，有长度k+1 的相同前缀后缀。
但如果pk != pj 呢？说明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。换言之，当pk != pj后，字符E前有多大长度的相同前缀后缀呢？很明显，因为C不同于D，所以ABC 跟 ABD不相同，即字符E前的模式串没有长度为k+1的相同前缀后缀，也就不能再简单的令：next[j + 1] = next[j] + 1 。所以，咱们只能去寻找长度更短一点的相同前缀后缀。
结合上图来讲，若能在前缀“ p0 pk-1 pk ” 中不断的递归前缀索引k = next [k]，找到一个字符pk’ 也为D，代表pk’ = pj，且满足p0 pk’-1 pk’ = pj-k’ pj-1 pj，则最大相同的前缀后缀长度为k’ + 1，从而next [j + 1] = k’ + 1 = next [k’ ] + 1。否则前缀中没有D，则代表没有相同的前缀后缀，next [j + 1] = 0。
那为何递归前缀索引k = next[k]，就能找到长度更小的相同前缀后缀呢？这又归根到next数组的含义。为了寻找长度相同的前缀后缀，我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配，如果pk 跟pj 失配，，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[ next[k] ]跟pj还是不匹配，则下一步用p[ next[ next[k] ] ]去跟pj匹配。相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更小的相同前缀后缀，要么没有长度更小的相同前缀后缀。
所以，因最终在前缀ABC中没有找到D，故E的next 值为0：
模式串的后缀：ABDE模式串的前缀：ABC前缀右移两位： ABC
读到此，有的读者可能又有疑问了，那能否举一个能在前缀中找到字符D的例子呢？OK，咱们便来看一个能在前缀中找到字符D的例子，如下图所示：
给定模式串DABCDABDE，我们很顺利的求得字符D之前的“DABCDAB”的各个子串的最长相同前缀后缀的长度分别为0 0 0 0 1 2 3，但当遍历到字符D，要求包括D在内的“DABCDABD”最长相同前缀后缀时，我们发现pj处的字符D跟pk处的字符C不一样，换言之，前缀DABC的最后一个字符C 跟后缀DABD的最后一个字符D不相同，所以不存在长度为4的相同前缀后缀。
怎么办呢？既然没有长度为4的相同前缀后缀，咱们可以寻找长度短点的相同前缀后缀，最终，因在p0处发现也有个字符D，p0 = pj，所以p[j]对应的长度值为1，相当于E对应的next 值为1。void GetNext(char* p,int next[]) {int pLen = strlen(p);next[0] = -1;int k = -1;int j = 0;while (j < pLen – 1){//p[k]表示前缀，p[j]表示后缀if (k == -1 || p[j] == p[k]){++k;++j;next[j] = k;}else{k = next[k];}} }
5、next数组的优化
就算是一辆永久单车也能让你的梦想走很远。
