P3375 【模板】KMP字符串匹配 (KMP模板)
2024-08-31 07:56:32
题目描述
如题,给出两个字符串s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置。
为了减少骗分的情况,接下来还要输出子串的前缀数组next。
(如果你不知道这是什么意思也不要问,去百度搜[kmp算法]学习一下就知道了。)
输入输出格式
输入格式:
第一行为一个字符串,即为s1
第二行为一个字符串,即为s2
输出格式:
若干行,每行包含一个整数,表示s2在s1中出现的位置
接下来1行,包括length(s2)个整数,表示前缀数组next[i]的值。
输入输出样例
输入样例#1:
ABABABC
ABA
输出样例#1:
1
3
0 0 1
说明
时空限制:1000ms,128M
数据规模:
设s1长度为N,s2长度为M
对于30%的数据:N<=15,M<=5
对于70%的数据:N<=10000,M<=100
对于100%的数据:N<=1000000,M<=1000000
思路:直接把s1接在s2后面进行KMP,枚举所有点若next[i]==s2.len则i是一个答案。
注意:串接时记得中间加一个符号防止影响结果(仔细想想)
代码注释:
1.字符串都以第0个开始
2.我这里的next[i]表示i点前面(不包含i)最长的前缀和后缀相同的字符串如:”abcabc”中 s[3]=’a’,next[3]=0,s[4]=’b’,next[4]=1(‘a’),s[5]=’c’,next[5]=2(“ab”)。
3.不明白KMP的可以尝试根据代码手算个数据体会一下(最好是画线段或矩形分情况思考一下),我不具体写了。
code1:
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=100005;
int next[MAX];
char s[MAX],a[MAX];
int main() {
scanf("%s",s+1);
getchar();
int len1=strlen(s+1);
scanf("%s",a+1);
int len2=strlen(a+1);
int len=len2;
a[++len]='*';
for(int i=1;i<=len1;i++)
a[++len]=s[i];
for(int i=2,j=0;i<=len;i++) {
while(j && a[i]!=a[j+1]) j=next[j];
if(a[i]==a[j+1]) j++;
next[i]=j;
}
for(int i=1;i<=len;i++) if(next[i]==len2) printf("%d\n",i-2*len2);
for(int i=1;i<=len2;i++) printf("%d ",next[i]);
return 0;
}
code2:
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
const int MAX=1000005;
int next[MAX<<1];
string s1,s2;
int main() {
cin>>s1;getchar();cin>>s2;
int len1=s1.length();
int len2=s2.length();
int len3=len1+len2+1;
s2+='#'+s1;//'#'即隔离符号
next[0]=-1;
int k=-1,j=0;
while(j < len3) {
if(k==-1 || s2[j]==s2[k]){//若k位于字符串首前或s[k]==s[j]显然有
k++,j++;
next[j]=k;
}
else k=next[k];//向前寻找一个小一点的但又可能满足条件的最大的
}
for(int i=0;i<len3;i++) if(next[i]==len2) printf("%d\n",i-len2*2);
for(int i=0;i<len2;i++) printf("%d ",next[i+1]);
return 0;
}
最新文章
- jquery简单原则器(匹配索引为指定值的元素)
- java中的方法重载与重写以及方法修饰符
- oracle 的PACKAGE恢复过程
- Codeforces 525E Anya and Cubes
- USB OTG简单介绍
- php获取分类以下的全部子类方法
- Paragraph 对象&#39;代表所选内容、范围或文档中的一个段落。Paragraph 对象是 Paragraphs 集合的一个成员。Paragraphs 集合包含所选内容、范围或文档中的所有段落。
- 201521123095 《Java程序设计》第6周学习总结
- 面试(二)---synchronized
- selenium获取百度账户cookies
- QT窗体的小技巧
- php 设计模式(转)
- .NET使用gRPC
- Redis master/slave,sentinel,Cluster简单总结
- Spring线程池的5个要素
- python winpdb远程调试
- 智读App-免费下载付费知识节目攻略
- linux 查看系统磁盘、内存大小
- TCP Socket 粘包
- hdu4686矩阵快速幂
热门文章
- git 添加到环境变量
- Spring Boot奇怪的问题:The Bean Validation API is on the classpath but no implementation could be found
- 逻辑斯蒂回归3 -- 最大熵模型之改进的迭代尺度法(IIS)
- Sinowal Bootkit 分析-中国红客网络技术联盟 - Powered by Discuz!
- 0x54 树形DP
- php basic syntax
- hdoj--3635--Dragon Balls(并查集记录深度)
- 第20章 Redis配置
- HTML中href、src区别
- rehat7.X下postgresql 11编译安装