首页 > 代码库 > Codeforces 471D 差分+kmp
Codeforces 471D 差分+kmp
题意 给出两个长度为n,m的a,b序列 问n中有多少个连续长度为m的序列,同时加/减去某一个数后和b相同
c序列同时加上/减去某个数,其相邻差不变.
算出相邻差,跑一遍kmp即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e6+20; int n,m,a[N],b[N],c[N],d[N]; int fail[N]; void getfail() { int i=0,j=-1; fail[0]=-1; while(i<m) { if(j==-1||d[i]==d[j]) { fail[i+1]=j+1; i++,j++; } else j=fail[j]; } } void KMP() { getfail(); int ans=0; int i=0,j=0; while(i<n) { // cout<<i<<‘ ‘<<j<<endl; if(j==-1||c[i]==d[j]) { i++,j++; if(j==m) { ans++; j=fail[j]; } } else j=fail[j]; } if(m==0) ans=n+1; cout<<ans<<endl; } int main() { while(cin>>n>>m) { for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<m;i++) scanf("%d",&b[i]); for(int i=0;i<n;i++) c[i]=a[i+1]-a[i]; for(int i=0;i<m;i++) d[i]=b[i+1]-b[i]; n--,m--; /* for(int i=0;i<n;i++) cout<<c[i]<<‘ ‘; cout<<endl; for(int i=0;i<m;i++) cout<<d[i]<<‘ ‘; */ KMP(); } return 0; }
Codeforces 471D 差分+kmp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。