KMP

int next[M];//M为模式串长度 void GetNext(char t[]){//next数组实质是模式串与自己匹配 next[0]=0; int j=0;//已匹配长度 for(int i=1;t[i];i++){//求next数组 while(j>0&&t[i]!=t[j])//利用next数组递归求最长相同真前后缀 j=next[j-1]; if(t[i]==t[j]) j++; next[i]=j; } } int KMP(char s[],char t[],int pos){//下标pos后匹配的首位置,过程与获取next数组一样 GetNext(t); int j=0;//模式串初始位置 int len=strlen(t); for(int i=pos;s[i];i++){ while(j>0&&s[i]!=t[j]) j=next[j-1]; if(s[i]==t[j]) j++; if(j==len) return i-j+1;//返回匹配首位置的下标 } return -1; }