KMP算法是在已知模式串的next函数值的基础上执行的，此函数值仅取决 于模式串本身而和相匹配的主串无关，相当于离线计算好模式串的next函数值，KMP搜索子串过程中产生“失配”时，保持主串指针不变，通过查表确定next[j]，移动模式串的指针到该位置再进行比较。主要是next函数值的确定。下面给出我整理的程序。

//KMP算法查找子串程序
#include
  
   
#include
   
     //根据模式串计算next函数值 void get_next(const char *pattern,int next[]) { unsigned int i = 0; int j = -1; next[0] = -1; while(i < strlen(pattern)) { if(j == -1 || pattern[i] == pattern[j]) { ++i; ++j; next[i] = j; // } else j = next[j]; } } //Index_KMP函数，string为主串，pattern为模式串，pos为主串中开始搜索的位置，next数组存储next函数值 int Index_KMP(const char *string,const char *pattern,int pos,int next[]) { unsigned int i = pos; int j = 0; unsigned int slen,plen; slen = strlen(string); plen = strlen(pattern); if(slen < plen) return 0; //unsigned int slen,plen; while(i < slen && j < plen) { if( j == -1 || string[i] == pattern[j]) { ++i; ++j; } else j = next[j]; } if(j >= plen) return i- plen; else return 0; } void main() { int i,j; int next[5] = {0}; get_next("abcac",next); //{-1,0,0,0,1} next函数值为-1表示主串指针向右移一位，再与模式串的首字符开始比较 for(i = 0;i < 5;i++) printf("%d ",next[i]); printf("\n"); i = Index_KMP("ababcabcacbab","abcac",0,next); j = Index_KMP("aba","abcac",0,next); printf("%d\n",i);//5 printf("%d\n",j);//0 }