牛客 栗酱的数列 (KMP)

牛客 栗酱的数列 (KMP)

传送门

题意：给a数组(n)，b数组(m)，模数k。问a有几个子串满足1<=i<=m，(a[i]+b[i])%k都相等。

题解：暴力匹配超时，这时候想到子串匹配算法KMP，但主要是有一个C=(a[i]+b[i])，要求一个串的值都等于C，而在一次匹配成功后，C可能会改变，故直接拿a数组建nex数组直接跳是错误的。

我们发现a[i]+b[i]a[i+1]+b[i+1]那么只要满足a[i]-a[i-1]b[i]-b[i-1]就行，上面与下面相等的模型，完全符合kmp板子。

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+7;
int T,n,m,k,ans;
int a[N],b[N];
int s[N],t[N];
int nex[N];
void kmp(){
	int l=0,r=1;
	nex[l]=-1;
	while(r<m){
		if(l==-1||s[l]==s[r]){
			l++;
			r++;
			nex[r]=l;
		}
		else{
			l=nex[l];
		}
	}
}

void gao(){
	int p1=0;
	int p2=0;
	while(p2<n){
		if(p1==-1||(s[p1]+t[p2])%k==0){
			p1++;
			p2++;
			if(p1==m){
				ans++;
				p1=nex[p1];
			}
		}
		else{
			p1=nex[p1];
		}
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
			a[i]%=k;
		}
		for(int i=0;i<m;i++){
			scanf("%d",&b[i]);
			b[i]%=k;
		}
		n--;
		m--;
		ans=0;
		for(int i=0;i<n;i++){
			t[i]=(a[i+1]-a[i]+k)%k;
		}
		for(int i=0;i<m;i++){
			s[i]=(b[i+1]-b[i]+k)%k;
		}
		kmp();
		gao();
		printf("%d
",ans);
	}
}