一、简介
在说改进的模式匹配（KMP）算法之前我们先说朴素的模式匹配：
其实很简单，就是两个字符串逐位比较。在模式匹配中：我们假定字符串P在字符串T中查找是否有匹配的。此时，称P为模式（Pattern）字符串，称T为目标（Target）字符串。
OK，我一般比较喜欢以实例说明问题。
T: a b d a b d a b c
P: a b d a b c
朴素的模式匹配算法
朴素的模式匹配算法就是用P和T依次比较，即为：
第一趟比较：
T: a b d a b d a b c
P: a b d a b c
发现第6个元素（下标为5）d和c不相等，第一趟结束，此时比较了6次（6个元素）。
第二趟比较：
T: a b d a b d a b c
P: a b d a b c
第一个元素就不相等，第二趟结束，此时比较了1次（1个元素）。
第三趟比较：
T: a b d a b d a b c
P: a b d a b c
第一个元素就不相等，第三趟结束，此时比较了1次（1个元素）。
第四趟比较：
T: a b d a b d a b c
P: a b d a b c
第一个元素相等，第二个元素也相等，第三、四、五、六都相等，匹配成功，第四趟结束，此时比较了6次（6个元素）。
匹配成功，共比较14次。但是这个是我们理想状态下的匹配方案，实际中字符串的长度远远不止这些。这种算法是一种带回逆的算法，成为朴素的模式匹配算法。
改进的模式匹配（KMP）算法
KMP算法就是消除了朴素匹配的回逆，利用一个失效函数（failure function）替代直接的回逆。思路如下：
第一趟比较：
T: a b d a b d a b c
P: a b d a b c
发现第6个元素（下标为5）d和c不相等。此时，进入一个P串的处理：
此时取出P串， a b d a b c 因为是c不和d不匹配，去掉此项，获得
a b d a b
此时判断 a b d a 是否与 b d a b 相等？ 不等，进入下一轮判断
此时判断 a b d 是否与 d a b 相等？ 不等，进入下一轮判断
此时判断 a b 是否与 a b 相等？ 相等，结束第一趟总体判断。
（先不要急，接下来我就会说为什么这样匹配和这样匹配的用途！）
然后直接拿d和字符串中不匹配的那一项进行比较。
以上就是KMP的流程，为什么要这样做？在一些串中，目标串会远远长于模式串，如果每次都江模式串和目标串一一比较。此时时间复杂度当增加，而且在模式串中会出现很多的无效匹配，相当于无用功。但是假如先在模式串中进行比较，因为模式串会远远短于目标串，所以会相当减少时间复杂度。
二、next数组的理解
对于KMP算法来说，重点就是 next数组 （也有叫覆盖函数，部分匹配表，lps数组等）。
总之就是 对模式串做预处理，而且该预处理只和 模式串(pattern)本身有关！
假设有模式串 pattern = “abababca”; 则有匹配表：
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
下面介绍《部分匹配表》是如何产生的。
首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。
字符串: "bread"
前缀： b , br, bre, brea
后缀: read, ead, ad , d
关于 next数组 （也有叫覆盖函数，部分匹配表，lps数组） 的通俗解释：”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，
"A"的前缀和后缀都为空集，共有元素的长度为0；
"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
下面举个例子
pattern “AABAACAABAA”, next[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
pattern “ABCDE”, next[] is [0, 0, 0, 0, 0]
pattern “AAAAA”, next[] is [0, 1, 2, 3, 4]
pattern “AAABAAA”, next[] is [0, 1, 2, 0, 1, 2, 3]
pattern “AAACAAAAAC”, next[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 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"); //测试用，可删除
}
三、KMP模式匹配算法
int Index_KMP(char *s,char *p,int pos,int next[])
/*利用模式串p的next函数，求p在主串中从第pos个字符开始的位置*/
/*若匹配成功，则返回模式串在主串中的位置（下标），否则返回-1。设模式串第一个字符的下标为0*/
{
int i,j,slen,plen;
i = pos-1;
j=-1;
slen = strlen(s);plen = strlen(p);
while(i<slen&&j<plen){
if(j==-1||s[i]==p[j]){++i;++j;}
else j = next[j];
}
if(j>=plen)return i-plen;
else return -1;
