首页 > 代码库 > #103. 子串查找
#103. 子串查找
内存限制:256 MiB时间限制:500 ms标准输入输出
题目类型:传统评测方式:文本比较
上传者: 匿名
提交提交记录统计讨论测试数据
题目描述
这是一道模板题。
给定一个字符串 A AA 和一个字符串 B BB,求 B BB 在 A AA 中的出现次数。
A AA 中不同位置出现的 B BB 可重叠。
输入格式
输入共两行,分别是字符串 A AA 和字符串 B BB。
输出格式
输出一个整数,表示 B BB 在 A AA 中的出现次数。
样例
样例输入
zyzyzyzzyz
样例输出
3
数据范围与提示
1≤A,B 1 \leq A, B1≤A,B 的长度 ≤106 \leq 10 ^ 6≤10?6??,A AA、B BB 仅包含大小写字母。
裸的KMP。
发现一前写错了一个地方
第40行的while一直写的是if。
但是在洛谷能AC,
估计是数据渣的一逼,,
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;const int MAXN=100000001;inline void read(int &n){ char c=‘+‘;int x=0;bool flag=0; while(c<‘0‘||c>‘9‘) {c=getchar();if(c==‘-‘)flag=1;} while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48,c=getchar();} flag==1?n=-x:n=x;}char a[MAXN];char b[MAXN];int la;int lb;int p[MAXN];int ans=0;void makep(){ int j=0; for(int i=1;i<lb;i++) { while(b[i]!=b[j]&&j>0) j=p[j-1]; if(b[i]==b[j]) j++; p[i]=j; }}void kmp(){ int j=0; for(int i=0;i<la;i++) { while(a[i]!=b[j]&&j>0) j=p[j-1]; if(a[i]==b[j]) j++; if(j==lb) ans++; } printf("%d",ans);}int main(){ scanf("%s%s",a,b); la=strlen(a); lb=strlen(b); makep(); kmp(); return 0;}
#103. 子串查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。