关键
差分处理,kmp查找
代码
#include <bits/stdc++.h>
using namespace std;
const int M=2e5+5;
int a[M],b[M];
int c[M],d[M];
int ne[M];
void init(int n) {
for(int i=2,j=0;i<=n;i++) {
while(j&&d[i]!=d[j+1])j=ne[j];
if(d[i]==d[j+1])j++;
ne[i]=j;
}
}
int find(int n,int m) {
int cnt=0;
for(int i=1,j=0;i<=n;i++) {
while(j&&c[i]!=d[j+1])j=ne[j];
if(c[i]==d[j+1])j++;
if(j==m) {
cnt++;
j=ne[j];
}
}
return cnt;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int TT;cin>>TT;
while(TT--) {
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
for(int i=1;i<n;i++)c[i]=((a[i+1]-a[i])%k+k)%k;
for(int i=1;i<m;i++)d[i]=((b[i]-b[i+1])%k+k)%k;
init(m-1);
cout<<find(n-1,m-1)<<'\n';
}
return 0;
}
//对呀,直接差分就行了,我在想啥呢
原文链接: https://www.cnblogs.com/basicecho/p/17047610.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/311534
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!