一，KMP算法
KMP算法，全称就是克努特-莫里斯-普拉特算法，是为了避免大量的重复遍历的情况。举个例子：
图 1 遍历对比匹配图1
图2 遍历对比匹配图2
从图1和图2中可以看出来，在图1中如果依次匹配，到5的时候匹配不成功，此时要回头重新匹配，从i=2,j=1的位置开始匹配，这就是回溯法的思想，就这样依次来回地回溯对比验证，最后才给出一个结论是否匹配成功。
图 3 思路启发一
思路启发一，在图3中可以看到在上面的匹配中，当i=j=5的时候，是S[5]与T[5]不相等，即不匹配，此时要重新进行匹配，分析可知S[1]=T[1],S[2]=T[2],S[3]=T[3],S[4]=T[4],而T[1]不等于T[2],T[1]不等于T[3],T[1]不等于T[4],T[2]也不等于T[3],T[2]也不等于T[4]，此时就不用将T[1]与S[1]\S[2]\S[3]\S[4]相匹配，直接让T[1]与S[5]进行匹配，即如图3下面的演示那样。这个时候提高了效率。
图4 思路启发二
这个思路启发二看上去肯定不符合启发一的情况，此时T[1]与S[2]是相等的，T[1]=T[2]，这个时候可以直接认为T[1]=S[2],匹配下一个，即匹配T[2]与S[3]，依次匹配下去就会出现匹配成功的结果。
图 5 思路启发三
在图5中可以看到，T[1]=T[2]=S[4]=S[5],此时可以直接从T[3]开始匹配，这样就提高了效率。
图6 思路启发四
在图6思路启发四中可以看到，根据前面的一二三的经验这个时候可以很明显从T[4]开始匹配。这样得出的一些规律就是KMP算法。问题是由模式串决定的，而不是目标串决定的。主要是为了保证 i 不再回溯。避免了效率低下的问题。
二，KMP算法的实现
1，首先get_next函数的编写
#include <stdio.h> typedef char* String; void get_next(String T,int *next) { int i = 1; int j = 0; next[1] = 0; while(i < T[0]) { if(0 == j || T[i] == T[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int main() { char str[255] = "ababaaaba"; int next[255]; int i = 1; str[0] = 9; get_next(str, next); for(i=1;i<10;i++) { printf("%d ",next[i]); } return 0; }
结果为
获取next数组的结果图
2，KMP算法的实现
//返回子串T在主串S第pos个字符之后的位置 int Index_KMP(String S,String T,int pos) { int i = pos; int j = 1; int next[255]; get_next(T,next); while(i<=S[0]&&J<=T[0]) { if(S[i] == T[j]) { i++; j++; if(T[i]!=T[j]) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } if(j>T[0]) { return i - T[0]; } else { return 0; } }
