传送门 题意 栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A’， 满足(a’1+b1)%k = (a’2+b2)%k = …… = (a’m + bm)%k。 思路 按照题目给的条件式只能暴力做，暴力做又超时。那么对满足式进行修改，(a[i]+b[i])%k=(a[i+1]+b[i+1])%k --> ((a[i]-a[i+1])%k+(b[i]-b[i+1])%k)%k = 0，问一个序列里有多少个满足条件的连续子序列，显然用kmp，匹配成功的条件改为(a[i]+b[i])%k == 0 就行。
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 7; int a[maxn], b[maxn]; int nex[maxn], n, m, k; void getnext(int s[]) { int len = m - 1; nex[0] = -1; int i = 0, j = -1; while (i < len) { if(j == -1 || s[i] == s[j]) {//这里匹配成功条件不变，失配指针是找相同的 i++; j++; nex[i] = j; } else j = nex[j]; } } int kmp(int t[], int s[]) {//文本串 模式串 int lent = n - 1, lens = m - 1, j = 0, i = 0, num = 0; while (i < lent && j < lens) { if(j == -1 || (t[i] + s[j]) % k == 0) {//匹配成功条件修改 i++; j++; } else j = nex[j]; if(j == lens) { num++; j = nex[j]; } } return num; } 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]); if(i > 0) a[i - 1] = ((a[i - 1] - a[i]) % k + k) % k; }//对k取余 for (int i = 0; i < m; i++) { scanf("%d", &b[i]); if(i > 0) b[i - 1] = ((b[i - 1] - b[i]) % k + k) % k; } getnext(b); printf("%d\n", kmp(a, b)); } }