1.练习项目 ：

题目描述:

小 Z 同学每天都喜欢斤斤计较，今天他又跟字符串杠起来了。

他看到了两个字符串 S1 S2 ，他想知道 S1 在 S2 中出现了多少次。

现在给出两个串 S1，S2(只有大写字母)，求 S1 在 S2 中出现了多少次。

输入描述

共输入两行，第一行为 S1，第二行为 S2。

1<len(s1)<len(s2)<106，字符只为大写字母或小写字母。

输出描述

输出一个整数，表示 S1 在 S2 中出现了多少次。

2.选择课程

在蓝桥云课中选择题库，选择题号2047并开始练习。

3.开始练习

（1）KMP算法  ：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
char s[N],p[N];
int nex[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>p+1;int m=strlen(p+1);
    cin>>s+1;int n=strlen(s+1);
    
    //get next
    nex[0]=nex[1]=0;
    for(int i=2,j=0;i<=m;i++){
        while(j&&p[i]!=p[j+1])j=nex[j];
        if(p[i]==p[j+1])j++;
        nex[i]=j;
    }
    
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        while(j&&s[i]!=p[j+1])j=nex[j];
        if(s[i]==p[j+1])j++;
        if(j==m)ans++;
    }
    
    cout<<ans<<'\n';
    return 0;
}

（2）字符串哈希

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
char s[N],p[N];
typedef unsigned long long ull;
const ull base = 131;
ull h1[N],h2[N],b[N];

ull getHash(ull h[],int l,int r)
{
    return h[r]-h[l-1]*b[r-l+1];
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>p+1;int m=strlen(p+1);
    cin>>s+1;int n=strlen(s+1);
    b[0]=1;
    for(int i=1;i<=n;i++){
        b[i]=b[i-1]*base;
        h1[i]=h1[i-1]*base+(int)p[i];
        h2[i]=h2[i-1]*base+(int)s[i];
    }
    int ans=0;
    for(int i=1;i+m-1<=n;i++){
        if(getHash(h1,1,m)==getHash(h2,i,i+m-1))ans++;
    }
    
    
    cout<<ans<<'\n';
    return 0;
}

（3）检验结果

对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。

（4）练习心得：注意每段代码末尾的分号是否存在 ，如不存在则需即使补充；输入法  是否切换为英语模式；语法是否错误。