给定两个数字序列，求a序列中每隔p个构成的p 1个序列中共能匹配多少个b序列。
例如1 1 2 2 3 3 每隔1个的序列有两个1 2 3
kmp，匹配时每次主串往前p个，枚举1到p为起点。
题目
代码语言：javascript复制#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[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=%dn",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: %dn",ca,KMP());
}
}
