栗酱的数列_牛客博客

题目描述

栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A'，
满足(a'1+b1)%k = (a'2+b2)%k = …… = (a'm + bm)%k。

输入描述:

第一行一个数T，表示有T组数据。
对于每组数据，
第一行三个整数，n, m, k。
第一行输入n个数, a1,a2,…,an, 表示A数列中的数，
第二行输入m个数, b1,b2,…,bm, 表示B数列中的数。

输出描述:

每一组数据输出一行，满足条件的连续子序列数量。

题解

对于这道题拿到手的第一感觉是暴力匹配吧，但复杂度太高。然后我们可以仔细想一想暴力的过程跟字符串匹配的暴力过程还是蛮像的，于是又想到字符串的经典算法————KMP。但是说我们怎么样去判断这两个串是否匹配呢？我们需要在给我们的式子上动一动手脚。
这个式子看起来很不好看的原因就是它的左右两边分别都有a数组和b数组里的东西，感觉处理起来很棘手，我们对于这个式子进行一下改变变成 $(a[i]+b[i])\%k-(a[i+1]+b[i+1])\%k=0$ ,也就是 $(a[i]-a[i+1]+b[i]-b[i+1])\%k=0$ 。那么我们就可以把 $a[i]-a[i+1]$ 处理出来看成整体然后愉快的进行KMP匹配啦。

代码

#include<bits/stdc++.h>
using namespace std;
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
int a[N],net[N],S[N],P[N];
int n,m,k;
/*
(a[i]+b[i]-a[i+1]-b[i+1])%k==0
*/
void getnext(int s[]){
    int i=0,j=-1,len=m-1;
    net[0]=-1;
    while(i<len){
        if(j==-1||s[i]==s[j]){
            net[++i]=++j;
        }
        else j=net[j];
    }
}
int kmp(int p[],int s[]){
    int ans=0;
    getnext(s);
    int i=0,j=0;
    int len_p=n-1,len_s=m-1;
    while(i<len_p&&j<len_s){
        if(j==-1||(p[i]+s[j])%k==0)++i,++j;
        else j=net[j];
        if(j==m-1)ans++,j=net[j];
    }
    return ans;
}
////////////////////////////////////////////////////////////////////////
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;++i)scanf("%d",&a[i]);
        for(int i=0;i<n-1;++i)P[i]=((a[i]-a[i+1])%k+k)%k;
        for(int i=0;i<m;++i)scanf("%d",&a[i]);
        for(int i=0;i<m-1;++i)S[i]=((a[i]-a[i+1])%k+k)%k;
        printf("%d\n",kmp(P,S));
    }
}

/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/