KMP算法用于字符串模式匹配，目标串T=[T1.....Tn]，模式串P=[P1....Pm]，这里n>=m，i代表T的索引指针，j代表P的索引指针，传统字符串匹配算法，在Ti!=Pj的时候，i指针需要回退到i-j的位置，同时j回退到0，也就是模式串P开始的位置，这样传统算法的匹配过程的复杂度就是O(m*n)。其实在Ti!=Pj的时候，i指针不需要回退，[Ti-j+1...Ti-1]和[P1....Pj-1]是相等的，可能只需要让j回退到中间的某个位置k，使得T[1....k]=T[j-k,j-1]。这个过程相当于，把已经匹配的P[1....j-1]，找出最长的相等的前缀和后缀。
从上图中可以看出，模式串P，目标串T，在i=9，j=5的位置，字符不匹配，这时传统的做法是将i回退到这轮匹配开始的字符i=5的下一个字符，i=6，同时将j回退到0的位置。但是我们发现已经匹配的T[5....8]=P[0....3]，把相等的部分记成字符串集合J[0....3]，可行的一种做法就是：把T模式串的i位置之前的一部分看成是刚才J串的后缀，把P串开始的一部分看做是J串的前缀，那么如果这个前缀和后缀相等的话，那么j指针回退到这个J串的最后的位置即可，因为P前缀已经保证了T后缀相等，i指针不用动，j指针移动到P模式串前缀的后一个位置即可，在尝试T[i]和P[j]的匹配。总之，在字符串匹配过程中，模式串P，T已经匹配的部分，通过这个P，T共有的部分，可以推测出，T的每个位置，后缀串和前缀串相等的最大长度。
KMP算法的精髓就是记录模式串中前缀最后位置的next数组，我的理解是next[i]：i表示字符串后缀最后的位置，前缀开始的位置是0，k表示后缀开始的位置，P[0......i-k] =P[k.....i],这个next[i]就等于i-k。
如上图，模式串P=''abcaabc''，next[6]表示以c为结尾的P串的后缀，以a开始的前缀，是的这个前缀和后缀相等，那么c的位置相对于前缀的位置，这个前缀中的位置就是next[6]的值。
代码：
void get_next(char* s,int* next) //s表示模式串，next表示next数组的头指针
{
int length=strlen(s);
int i=1,j=0;
//i表示模式串的每一个元素的指针，每次加1递增，j表示前缀串中，每一个元素的位置。
next[0]=-1;
for(;i
字符串匹配：
//target是目标串，s是模式串，data是next数组
void find(char *target,char *s,int* data){
int i=0; //i是目标串的指针
int j=0; //j是模式串的指针
for(;i
说明，这里next数组中每个元素的含义是，这个元素在前缀字符串中的位置，所以在当前位置j不匹配的时候，应该首先取得匹配的字符串中前缀的最后的位置，然后新的j的值就应该是j+1的位置，j之前的元素就是原来匹配字符串的前缀。如图2中所示，如果在j=6的位置元素匹配失败，那么j=6元素之前的字符串中，b元素的位置是5，应该对应到前缀中j=1的位置，那么j的位置应该是j+1=2，再和目标串去匹配。
验证程序：
总结：相对于朴素的字符串匹配算法，复杂度为O(m*n),KMP算法中目标串的指针不用回缩，复杂度为O(m+n),大大减小了模式串搜索的复杂度。
参考文章：
1.http://blog.csdn.net/v_july_v/article/details/7041827