Codeforces Round #269 (Div. 2) D

本文主要是介绍Codeforces Round #269 (Div. 2) D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

D. MUH and Cube Walls

        题意：给两个数列a1~an，b1~bw，问在b数列中每两个相邻的数的增减情况是否和a数列中的某些段的增减情况相吻合。求共有几处吻合。

        思路：KMP算法。把字符的匹配换成了增减量的匹配，预处理相邻数的差，注意第一个数没有上一个数，所以不用匹配第一个数。还有就是b的长度为1的情况需要考虑。

#include <iostream>      
#include <stdio.h>      
#include <cmath>      
#include <algorithm>      
#include <iomanip>      
#include <cstdlib>      
#include <string>       
#include <vector>      
#include <queue>      
#include <stack>      
#include <map>    
#include <set>    
#include <string.h>
#include <ctype.h>      using namespace std;    #define ll long longint a[200010];
int aa[200010];
int b[200010];
int bb[200010];
int next[200010];int main(){int n ,w;while(cin>>n>>w){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}aa[1]=0;for(int i=2;i<=n;i++){aa[i-1]=a[i]-a[i-1];}for(int i=1;i<=w;i++){scanf("%d",&b[i]);}bb[1]=0;for(int i=2;i<=w;i++){bb[i-1]=b[i]-b[i-1];}next[1]=0;int j=0;for(int i=2;i<w;i++){while(j&&bb[j+1]!=bb[i]){  j=next[j]; }if(bb[i]==bb[j+1])j++; next[i]=j; }  int ans=0;j=0;for(int i=1;i<n;i++){while(j&&bb[j+1]!=aa[i]){j=next[j];  }  if(aa[i]==bb[j+1])j++;if(j==w-1){ans++;j=next[j];}}if(w==1){cout<<n<<endl;}else{cout<<ans<<endl;}}return 0;
}

这篇关于Codeforces Round #269 (Div. 2) D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---