【hdu 5918】Sequence I(KMP)

时间:2022-12-08 06:46:50

给定两个数字序列,求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 1000005
int t,n,m,p;
int nex[N];
int a[N],b[N];
using namespace std;
void getNext(){
int i=0,k=-1;
nex[]=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());
}
}