C++课后习题训练记录Day137

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