串的模式匹配

串的模式匹配(KMP)

设s和t是给定的两个串,在主串s中找到等于子串t的过程称为模式匹配。

如果在s中找到等于t的子串,则称匹配成功,函数返回t在s中的首次出行的存储位置,否则匹配失败,返回-1。

t也称模式串,s称为目标串,为了方便,设字符的长度存放在0号单元,串值从1号单元往后存放,这样字符序号与存储的位置一致。

简单算法

首先将s1与t1进行比较,若不同,就将s2与t1进行比较…直到s的某一个字符si和t1相同,再将他们之后的字符进行比较,若也相同,则如此继续往下比较,当s的某一个字符si与t的字符tj不同时,则s返回到本趟开始字符的下一个字符,即si-j+2,t返回到t1,继续开始下一趟的比较,重复上述过程。若t中的字符全部比完,则说明本趟匹配成功,本趟的起始位置是i-j+1或i-t[0],否则,匹配失败。

完整代码

int Index(SString S,SString T){

int i=1,j=1;

while(i<=S[0]&&j<=T[0]){//第0个位置存放的是长度

if(S[i]==T[j])1{

i++;

j++;

}else{

i=i-j+2;

j=1;

}

}

if(j>T[0])

return i-T[0];//return i-j+1也是完全ojbk的

else

return 0;

}

最好情况下时间复杂度是O(n+m)

最坏情况下时间复杂度是O(n*m)

KMP算法

int Index(SString S,SString T){

int i=1,j=1;

while(i<=S[0]&&j<=T[0]){//第0个位置存放的是长度

if(j==0||S[i]==T[j])1{

i++;

j++;

}else{

J=next[j];

}

}

if(j>T[0])

return i-T[0];//return i-j+1也是完全ojbk的

else

return 0;

}

Void get_next(char T[],int next[]){

I=1;

Next[1]=0;

J=0;

While(i<=T[0]){

If(j=0||T[i]==T[j]){

i++;

J++;

Next[i]=j;

}else

J=next[j];

}

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注