KMP算法值用线性的复杂度查找字串,比传统的带有回溯色彩的算法高效。
下面是代码:
int KMP(char *T,char *P) { int posT,posP,lenT,lenP;//定义两个指针,分别指向T和P,初始化从0开始 posT=0,posP=0,lenT=strlen(T),lenP=strlen(P); while(posT<lenT&&posP<lenP) { if(posP==-1||T[posT]==P[posP])//只有两种情况向后++,1.字符匹配成功 2.第一个字符匹配不成功 { posP++,posT++; } else posP=next[posP];//找模式串前面的p0......pk最大的雨末尾k+1个元素相同的下一个位置 } if(posP==lenP)//但posP指针到达模式串的长度所在的位置,则说明找到了 { return posT-lenP;//放回第一个字母所在目的串的位置 } else { return -1; } }
next【】的求法也到了递推的方法。
void getNext(char *P) { int k,j,lenP; lenP=strlen(P); k=-1,j=0,next[0]=-1;//注意:k从-1开始,next[1]=0,比较P[2]和P[i],k,p始终指向匹配好的下一个点 while(j<lenP) { if(k==-1||P[k]==P[j])//只有两种情况k和j++ { k++,j++,next[j]=k; } else k=next[k];//否则找最大的满足条件的k, } }