KMP算法的核心就是利用已匹配的信息来指导模式串的匹配。这里的已匹配信息叫做部分匹配表，也叫做next数组。其存储的是字符串的前缀后缀重合部分的字符数。以此来控制模式串的移动位数。
next数组生成的步骤：
假设模式串是“ABABABB”
前缀：除最后一个字符外，例如，A、AB、ABA、ABAB、ABABA、ABABAB
后缀：除第一个字符外，例如，B、BB、ABB、BABB、ABABB、BABABB
1.字符串“A”无前缀后缀，所以 next[1]=0 (至于为什么next数组从1开始，代码会讲到，暂且不要纠结)
2.字符串“AB”前缀“A”和后缀“B”不相等，所以 next[2]=0
3.字符串“ABA”前缀“A”和后缀“B”相等，所以 next[3]=1
4.字符串“ABAB”前缀“AB”和后缀“AB”相等，所以 next[4]=2
5.字符串“ABABA”前缀“ABA”和后缀“ABA”相等，所以 next[5]=3
6.字符串“ABABAB”前缀“ABAB”和后缀“ABAB”相等，所以 next[6]=4
因为最后一个并无指导意义，所以不需理它。
接下来看详细的代码：
/*
* function 生成部分匹配表，next数组
* param subStr 模式串，子串
* param next next数组，部分匹配信息表
* param len next数组的长度，一般就是模式串的长度
* return 无
*/
void GetNext(const char* subStr, int* next, int len)
{
memset(next, 0, len);
int prefix = -1; //前缀
int suffix = 0; //后缀
next[0] = -1; //第一个元素只是用来控制prefix和suffix后移的
while (suffix < len - 1)//当比较到最后一个字符的时候退出循环
{
/*
当prefix == -1的时候表示要从prefix=0，suffix=1开始比较
若prefix ！= -1，表示前缀和后缀已经有重合的了，接着往后移比较
例如：subStr="ABABABB"
1.prefix=-1,往后移，prefix=0，suffix=1，next[1] = 0,表示字符串‘A’前缀后缀无重合
2.prefix=0,比较subStr[0]和subStr[1]('A'和'B'),不相等，把prefix重新置为next[prefix](next[0]==-1)
3.prefix=-1,往后移，prefix=0，suffix=2，next[2] = 0,表示字符串‘AB’前缀后缀无重合
4.prefix=0，比较subStr[0]和subStr[2]('A'和'A'),相等，继续往后移，prefix=1，suffix=3，next[3]=1
表示字符串"ABA"有一个字符前缀后缀相等('A'和'A')
5.prefix=1，比较subStr[1]和subStr[3]('B'和'B'),相等，继续往后移，prefix=2，suffix=4,next[4]=2
表示字符串"ABAB"有两个字符前缀后缀相等('AB'和'AB')
6.prefix=2，比较subStr[2]和subStr[4]('A'和'A'),相等，继续往后移，prefix=3，suffix=5,next[5]=3
表示字符串"ABABA"有三个字符前缀后缀相等('ABA'和'ABA')
7.prefix=3，比较subStr[3]和subStr[5]('B'和'B'),相等，继续往后移，prefix=4，suffix=6,next[6]=4
表示字符串"ABABAB"有四个字符前缀后缀相等('ABAB'和'ABAB')
8.当suffix=6最后一个的时候，就不需要比较了，因为KMP算法中最后一个并无指导匹配的作用,因为一旦前6个匹配成功，最后一个
就算不成功，用到的也是前一个的部分匹配信息，若是成功那就直接返回了，所以求next数组的时候，最后一个的信息省略
*/
if (prefix == -1 || subStr[prefix] == subStr[suffix])
{
++prefix, ++suffix;
next[suffix] = prefix;
printf("%d ", next[suffix]); //测试用，可删除
}
else
prefix = next[prefix];
}
printf("\n"); //测试用，可删除
}测试结果如图： 
顺序表的动态增长（C++、JAVA）
栈、递归、循环的关系（C++、JAVA）
栈应用之中缀转后缀表达式计算（C++、JAVA）
栈应用之中缀转后缀表达式（C语言版）
约瑟夫问题详解+源码
线性表之循环队列
线性表之链队列
线性表之顺序队列
线性表之链栈
线性表之顺序栈
线性表之双向链表
线性表之循环链表
线性表之单链表
线性表之顺序表