D.E.Knuth、J.H.Morris和V.R.Pratt，发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称为KMP算法
一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。
KMP算法：可以实现复杂度为O(m+n)
算法代码如下：
获得子串的nextval数组:
void get_nextval (String T, int *nextval) {
int i, j;
i=1;
j=0;
nextval[1]=0;
while (i<T[0]) {/*此处T[0]表示子串的长度*/
if(j == 0 || T[i] == T[j]) {/*T[i]表示后缀的单个字符,T[j]表示前缀的单个字符*/
++i;
++j;
if(T[i] != T[j])/*若当前字符与前缀字符不同*/
nextval[i] = j;/*则当前的j为nextval在i位置的值*/
else
nextval[i] = nextval[j]; /* 如果与前缀字符相同，则将前缀字符的nextval值赋值给nextval在i位置的值*/
}
else
j = nextval[j];
}
}
获得要匹配的子串在主串中的位置
/* 返回子串在主串中第pos个字符之后的位置。若不存在，则返回0*/
/*T非空，1<=pos<=StrLength(S)。*/
int Index_KMP(String S, String T, int pos) {
int i = pos;/*i用于主串当前位置下标，若pos不为1，则从pos位置开始匹配*/
int j= 1;/*j用于子串T中当前位置下标值*/
int next[255];/*定义一next数组*/
get_nextval(T, next);/*对子串作分析，得到next数组*/
while( i <= S[0] && j <= T[0] )/*所i小于主串的长度且j小于子串的长度时，循环继续*/
{
if (j==0 || S[i] == T[j])/*j=0或两字母相等继续*/
{
++i;
++j;
}
else{/*指针后退重新开始匹配*/
j = next[j];/*j退回合适的位置，i值不变*/
}
}
if(j > T[0])
return i-T[0];
else
return 0;
}
