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最大......
阅读全文