概念：
是一种由三人设计的线性时间字符串匹配算法。这个算法的高效之处在于当在某个位置匹配不成功的时候可以根据之前匹配的结果从模式字符串的另一个位置开始，而不必从头开始匹配字符串。
与BF算法相比的优点：
KMP算法巧妙地消除了指针的回溯，只需要确定下次匹配的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
引入next[]数组：
next[j]的值表示P[0-j-1]中最长后缀的长度等于相同字符序列的前缀。
定义：next[j]=-1(j=0)；
如： a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
算法思想：
在匹配过程中，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则i右移1位，将j置0，继续进行比较。
代码：
int KMPMatch(char *s,char *p){ int next[100],i,j; i=0; j=0; getNext(p,next); while(i<strlen(s)){ if(j==-1||s[i]==p[j]){ i++; j++ } else j=next[j];//消除了指针i的回溯 if(j==strlen(p)) return i-strlen(p); } return -1; } 求算next[]数组的值：（采用递推的思想） void getNext(char *p,int *next){ int j,k; next[0]=-1; j=0; k=-1; while(j<strlen(p)-1){ if(k==-1||p[j]==p[k]){ j++; k++; next[j]=k; } else k=next[k]; } }