KMP模式匹配算法

功能：在O（n+m）的时间内，找出B串中包含多少个子串A，并得到首地址
思路：主要分为一下两个步骤
1.计算Next数组，Next数组保存了A串自我匹配的结果，用于在与B串匹配时，一旦出现失配的情况，可以找到最近的可以继续匹配的位置，而不需要从头开始
2.计算F数组，F数组保存了B[i]的后缀能与A串的前缀能匹配的最大长度
详见 进阶指南P70-71
代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
int Next[10005],f[1000005];
char ss[1000005],s[10005];

void solve(){
    int ans=0;
    scanf("%s",s+1);
    scanf("%s",ss+1);
    int l=strlen(s+1);
    int ll=strlen(ss+1);
    for (int i=2,j=0;i<=l;++i){
        while (j>0 && s[i]!=s[j+1]) j=Next[j];
        if (s[i]==s[j+1]) j++;
        Next[i]=j;
    }
    for (int i=1,j=0;i<=ll;++i){
        while (j>0&&ss[i]!=s[j+1] || j==l) j=Next[j];
        if (ss[i]==s[j+1]) j++;
        f[i]=j;
        if (j==l) ans++;
    }
    printf("%d\n",ans);
}

int main(){
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}

例题

循环前缀

题面见进阶指南P72
可以利用Next数组，如果一段字符串的前缀和后缀相匹配，而且剩余部分是总长度的因数，那么该字符串就是循环串，证明见进阶指南P72~73
代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
int Next[1000005],f[1000005],t;
char s[1000005];

bool solve(){
    t++;
    int len;
    scanf("%d",&len);
    if (len==0) return 0;
    scanf("%s",s+1);
    for (int i=2,j=0;i<=len;++i){
        while (j>0 && s[i]!=s[j+1]) j=Next[j];
        if (s[i]==s[j+1]) j++;
        Next[i]=j;
    }
    printf("Test case #%d\n",t);
    for (int i=2;i<=len;++i){
        if ((i%(i-Next[i])==0) && i!=(i-Next[i])) printf("%d %d\n",i,(i/(i-Next[i])));
    }
    puts("");
    return 1;
}

int main(){
    while (solve());
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/78/