题目描述

这是一道模板题。

给定一个字符串 $A$ 和一个字符串 $B$，求 $B$ 在 $A$ 中的出现次数。$A$ 和 $B$ 中的字符均为英语大写字母或小写字母。

$A$ 中不同位置出现的 $B$ 可重叠。

输入格式

输入共两行，分别是字符串 $A$ 和字符串 $B$。

输出格式

输出一个整数，表示 $B$ 在 $A$ 中的出现次数。

zyzyzyz
zyz

3

数据范围与提示

$1 \leq A, B$ 的长度 $\leq 10 ^ 6$，$A$、$B$ 仅包含大小写字母。

#include<bits/stdc++.h>
//#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=1e6+10;
int T,n,m;
int nxt[N];
char s1[N],s2[N];
void get_nxt(int *nxt,char *s,int &len){
    nxt[0]=-1;
    int i=-1,j=0;
    for(;j<n;){
        if(i==-1||s[i]==s[j])nxt[++j]=++i;
        else i=nxt[i];
    }
}
void kmp(char *s1,char *s2,int &n,int &m){
    int i=0,j=0,ans=0;
    for(;j<n;){
        if(i==-1||s1[j]==s2[i])++i,++j;
        else i=nxt[i];
        if(i==m)++ans;
    }
    cout<<ans<<'\n';
}
main(){
    cin>>s1>>s2;
    n=strlen(s1),m=strlen(s2);
    get_nxt(nxt,s2,m);
    kmp(s1,s2,n,m);
}