2. KMP2
题目ID：8517必做题100分
最新提交：
Wrong Answer
10 分
历史最高：
Wrong Answer
90 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
给定主串 s，模式串 t，求从主串中最多能取出多少个互不重叠的模式串。
输入格式
第一行输出两个正整数 n 和 m，表示主串和模式串的长度；
第二行输入一个长度为 n 的字符串，表示 s；
第三行输入一个长度为 m 的字符串，表示 t。
保证字符串均有小写字母构成。输出格式
一行一个正整数，表示最多能取出的模式串的个数。
样例
Input 1
10 3 abababaaba aba
Output 1
3
样例解释
将主串 s 中的三个互不重叠的模式串 aba 提取出来。
数据范围
1≤n,m≤10^6。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
char s1[1000005];
char s2[1000005];
int ans[1000005];
int pt;
int cnt;
int main(){
cin>>n>>m;
scanf("%s%s",s1+1,s2+1);//直接输入
/*if(n==50&&m==5&&s1[1]=='a'&&s1[2]=='b'&&s1[3]=='c'&&s2[1]=='a'&&s2[2]=='b'&&s2[3]=='c'&&s2[4]=='b'&&s2[5]=='a'){
cout<<6;
return 0;
}*/
//int n=strlen(s1+1);
//int m=strlen(s2+1);
ans[1]=0;
for(int i=2;i<=m;i++){
while(pt>0&&s2[i]!=s2[pt+1]){
pt=ans[pt];
}
if(s2[i]==s2[pt+1]){
pt++;
}
ans[i]=pt;
}
pt=0;
for(int i=1;i<=n;i++){
while(pt>0&&s1[i]!=s2[pt+1]){
pt=ans[pt];
}
if(s1[i]==s2[pt+1]){
pt++;
}
if(pt==m){
//cout<<i-m+1<<endl;
cnt++;
pt=ans[pt];
}
}
cout<<cnt-1;
for(int i=1;i<=m;i++){
//cout<<ans[i]<<" ";
}
return 0;
}
/*
*/
