文档介绍：使用KM
法求子串出现次数
算法：对应长度为的目标串和长度为的模式串，算法的复杂度是其中的时间用于需找模式串的失效
函数，的时间用于匹配。算法思想说起来比较麻烦，但是并不复杂，参考数据结构的书吧。
下面给出的代码
使用KM
法求子串出现次数
算法：对应长度为的目标串和长度为的模式串，算法的复杂度是其中的时间用于需找模式串的失效
函数，的时间用于匹配。算法思想说起来比较麻烦，但是并不复杂，参考数据结构的书吧。
下面给出的代码
和子串出现次数代码
其中的复杂度是，整体复杂度也是
Pos=0,ptP
p
ppp
pos=0,ptpos=0,count=0
p
pp
p
p
else{
if(ptPos==0)tgPos++;
elseptPos=f[ptPos-1]+1;
}
if(ptPos>=ptLen){
count++;
ptPos=f[ptLen-1]+1;
}
}
returncount;
}
intmain()
{
constchar*tag="abcbcbcbc";
constchar*pat="bcbc";
intlen=strlen(pat);
int*f=newint[len];
fail(pat,f);
cout<<"失效函数位置:\n";
for(inti=0;i<len;++i)
cout<<f[i]<<'\n';
cout<<子串第一次出现的位置:\n";
cout<<search(tag,pat,f)<<'\n';
cout<<"子串出现的次数：\n";
cout<<count(tag,pat,f)<<'\n';return0;
}