在上一节里面我们知道BF算法。
现在我们来讲解KMP算法。他的思路如下
每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式想右滑动进可能远的一段距离后，继续比较。
上面那个思路是书上的话，到底是什么意思！！！我们现在用人话来讲解。下面大家跟着我的思路（这节KMP是数据结构的第一个难点，请大家认真对待）
KMP算法的目的：就是为了避免不必要的回溯，这里的不必要的回溯只由模式串（也就是T）决定，与目标串无关（也就是S）。
那么问题来了，什么是不必要的回溯。
上节课将到的BF算法。当匹配不成功时，他就把模式串的指针指向开头。然后一个个重新匹配，这就是回溯。
这里引进了一个next[]数组，我们先来看下书中这个图，这图到底是怎么画出来的（数据结构C语言版严蔚敏2016年12月46次印刷）
这里的next[j]有些教程把这个地方填写K，意思是告诉大家数据结构里面第三行可以用next[j]或K都可以。
首先我们来看这个j是从1开始，一直到8，那么就有个问题，0呢？
在这本书上，为了更换的说明算法把串的第一个设置为串的大小，并且省略掉最后‘/0’(C/C++里面串结尾都是'/0')
那么我们补充下图，如下所示：
那么我们来看下，这个next[j](部分教程用K表示)这个到底是怎么填的。
下面就直接告诉大家：
我们看模式串那一行：
j=1时模式串是a，next[j]对应为0(代码中有交代j==0,在所有的模式串里面第一个都为0，待会在代码里面会说明这个，现在大家先记着)。
j=2时模式串是b，next[j]对应为1，我们想想，当b比匹配失败后，我们要回到前面的模式串，那么只能是b前面的a，所以next[j]对应为1。
j=3时模式串是a，next[j]对应为1，这时我们看到了下标3前面的字符是a和b，他们没有相同的，回溯的话还是a，所以next[j]对应为1。
j=4时模式串是a，next[j]对应为2，这时我们看到下标4前的字符是aba,我们发现首串a和尾串a相同，那么他就是1+1=2。
j=5时模式串是b，next[j]对应为2，下标为5前的字符是abaa，这时首串a，尾串a，那么他就是1+1=2。
j=6时模式串是c，next[j]对应为3，下标为6前的字符是abaab,这时我们发现首串ab，尾串ab，那么他就是2+1=3。
j=7时模式串是a，next[j]对应为1，下标为7前的字符是abaabc，这时我们发现他首串和尾串不相同。那么就是0+1=1。
j=8时模式串是c，next[j]对应为2，下标为8前的字符是abaabca，这时我们发现首串和尾串相同的是a，那么就是1+1=2。
下面我们总结了一个规律：在KMP算法里面，next的填写看他前面的串，如果首串和尾串有一个相同则是1+1，如果有两个则是2+1，三个是3+1，第一个next始终是0。
大家next[j]会画了吧！
下面我们来看更重要的问题，为什么要next，这个next到底有什么用？
我们现在来看下书中利用模式的next函数进行匹配的过程示例就知道了（图如下）
这里我们看到：
第一趟当遇到第二个的时候也就是c时与模式里的第二个不一样，所以退回nex[2]也就是1的地方。
第二趟主串的第一个和模式的第一个都不相等，什么i++，j++。
第三趟我们发现abaab都相等，但下面一个，也就是j=6时，发现不相等，此时next[6]也就是3（待会就解释这个）
第四趟就匹配成功了。
现在问题来了，为什么可以这么做，这个next到底是什么东西！我们发现next表示下标为某个数前，相同的字符数+1，这个+1的意思就是指向相同首串的后面那个（比如abaab）ab是首串和尾串都相同的。所以移到第三个，就是是a这个位置。
所以我们貌似发现了一个规律。当匹配不成功时，这个next将回到模式想右滑动进可能远的一段距离后，继续比较。
这就是书上：
每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式想右滑动进可能远的一段距离后，继续比较。
的说明。下面是代码：
void get_next(SString T, int *next) { int i = 1; next[1] = 0; int j = 0; while (i < T[0]) { if (j == 0 || T[i] == T[j]) { ++i; ++j; next[i] = j; } else j = next[j]; }}int Index_KMP(SString S, SString T, int pos) { // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 // KMP算法。其中，T非空，1≤pos≤StrLength(S)。 int next[255]; int i = pos; int j = 1; get_next(T, next); while (i <= S[0] && j <= T[0]) { if (j == 0 || S[i] == T[j]) // 继续比较后继字符 { ++i; ++j; } else // 模式串向右移动 j = next[j]; } if (j > T[0]) // 匹配成功 return i - T[0]; else return 0;} // Index_KMP这里我们就可以解释：为什么模式串第一个next总是一，因为代码中给它了一个特别的条件。这代码不用多解释，大家也能看懂吧。
下面是KMP的优化：
例如模式‘aaaab’
主串‘aaaarcde’
next图如下：
j 0 1 2 3 4 5 模式 5 a a a a b next[j] 0 1 2 3 4 进行匹配的时候我们发现主串的aaaar当到这个r的时候，不匹配，他先回到next[4],然后next[3],next[2],next[1],next[0],
这种是不好的效率，因为我们发现这模式串里面前4个都一样的。所以我们可以对他修改为这样。
当计算的过程中如果之前的前缀元素都是相等的话会回溯到前缀元素的next值那里去。
所以，可以改成如下
j 0 1 2 3 4 5 模式 5 a a a a b next[j] 0 0 0 0 4 所以我们可以对get_next函数进行修改，如下所示：
void get_next(SString T, int *next) { int i = 1; next[1] = 0; int j = 0; while (i < T[0]) { if (j == 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) next[i] = ; else next[i] = next[j]; } else j = next[j]; }}
新闻热点
疑难解答
