数据结构串匹配十大经典算法
发布网友
发布时间：2022-04-29 22:54
共1个回答
热心网友
时间：2022-05-23 06:57
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。
int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函数值求T在主串S中第pos 个字符之后的位置的KMP算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函数：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next
我现在只有这两个答案。
参考资料：<<数据结构>>（C语言版）严蔚敏 吴伟民 编 清华大学出版社
