Oulipo

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1054 字

KMP统计模式串在文本串中出现次数

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1455
// 题意：先给 T，随后 T 组每行两个大写串 s1、s2，输出 s1 在 s2 中的出现次数（可重叠）。
// 思路：对 s1 求前缀函数 nxt，再扫描 s2 做 KMP，每凑满一次完整匹配计数加一并回退到 nxt[m] 以支持重叠。
// 复杂度：O(|s1|+|s2|) 时间 / O(|s1|) 空间
// 易错点：匹配后 j 必须回退到 nxt[m] 而不是 0，否则漏掉重叠出现；s2 长度可达 1e6，不能逐字符 cin。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if(!(cin>>T)) return 0;
    while(T--){
        string s1,s2;
        if(!(cin>>s1)) return 0;
        if(!(cin>>s2)) return 0;
        int m=(int)s1.size();
        vector<int> nxt(m+1,0);
        for(int i=1;i<m;i++){
            int j=nxt[i];
            while(j>0&&s1[i]!=s1[j]) j=nxt[j];
            if(s1[i]==s1[j]) j++;
            nxt[i+1]=j;
        }
        long long ans=0;
        int j=0;
        for(int i=0;i<(int)s2.size();i++){
            while(j>0&&s2[i]!=s1[j]) j=nxt[j];
            if(s2[i]==s1[j]) j++;
            if(j==m){
                ans++;
                j=nxt[m];
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Oulipo

正文

一本通·提高篇的其它内容