首页 > 代码库 > 【hdu 5918】Sequence I（KMP）
【hdu 5918】Sequence I（KMP）
给定两个数字序列，求a序列中每隔p个构成的p+1个序列中共能匹配多少个b序列。
例如1 1 2 2 3 3 每隔1个的序列有两个1 2 3
kmp，匹配时每次主串往前p个，枚举1到p为起点。
题目
#include<bits/stdc++.h>#define N 1000005int t,n,m,p;int nex[N];int a[N],b[N];using namespace std;void getNext(){ int i=0,k=-1; nex[0]=k; while(b[i]){ while(k!=-1 && b[i]!=b[k])k=nex[k]; nex[++i]=++k; }}int KMP(){ int ans=0; for(int q=0;q<p;q++){ int i=q,j=0; while(i<n){ while(-1!=j && a[i]!=b[j])j=nex[j]; i+=p;j++; if(j>=m){ ans++; j=nex[j]; } } // printf("ans=%d\n",ans); } return ans;}int main(){ //freopen("1008.in","r",stdin); scanf("%d",&t); for(int ca=1;ca<=t;ca++){ memset(a,0,sizeof a); memset(b,0,sizeof b); memset(nex,0,sizeof nex); scanf("%d%d%d",&n,&m,&p); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<m;i++) scanf("%d",&b[i]); getNext(); printf("Case #%d: %d\n",ca,KMP()); }}
【hdu 5918】Sequence I（KMP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。