2023年7月20日发(作者：)

使⽤KMP算法求⼦串出现次数1. KMP算法：对应长度为n的⽬标串和长度为m的模式串，kmp算法的复杂度是o(m+n).其中o(m)的时间⽤于需找模式串的失效函数，o(n)的时间⽤于匹配。算法思想说起来⽐较⿇烦，但是并不复杂，参考数据结构的书吧。2. 下⾯给出kmp的代码search()和⼦串出现次数代码count().其中count()的复杂度是o(n)，整体复杂度也是o(m+n).

#include #include #include using namespace std;void fail(const char* pat, int* f){ const int len=strlen(pat); f[0]=-1; for (int j=1; j < len; j++){ if (pat[j] == pat[f[j-1]+1]) f[j] = f[j-1]+1; else { int i=f[j-1]; while ( i >=0 && pat[j] != pat[i+1] ) i = f[i]; if (pat[j] ==pat[i+1]) f[j] = i+1; else f[j] = -1; } }}int search(const char* tg, const char *pt, const int* f){ const int ptLen=strlen(pt); const int tgLen = strlen(tg); int tgPos=0,ptPos=0; for (; tgPos < tgLen && ptPos < ptLen;) { if (tg[tgPos] == pt[ptPos]){ ptPos++; tgPos++; } else { if (ptPos == 0) tgPos ++; else ptPos = f[ptPos-1] + 1; } } return ptPos < ptLen ? -1: tgPos - ptLen;}int count(const char* tg, const char *pt, const int* f){ const int ptLen=strlen(pt); const int tgLen = strlen(tg); int tgPos=0,ptPos=0,count=0; for (; tgPos < tgLen;) { if (tg[tgPos] == pt[ptPos]){ ptPos++; tgPos++; } else { if (ptPos == 0) tgPos ++; else ptPos = f[ptPos-1] + 1; } if (ptPos >= ptLen ){ count ++; ptPos=f[ptLen-1] +1; } } return count;}int main(){ const char *tag="abcbcbcbc"; const char *pat="bcbc"; int len=strlen(pat); int *f =new int[len]; fail(pat,f); cout <<"失效函数位置:n"; for(int i=0;i