Description

Input

Output

Data Constraint

Solution

• 觀察到條件是：

  Ak?i+1?Bi=Ak+j?1?Bj

• 移項后得：

  Ak?i+1?Ak+j?1=Bi?Bj

• 這樣條件就只與自己有關，且其實質就是差值恒定。

• 于是轉換條件，就有：

  Ai?Ai?1=Bj?Bj?1

• 那么我們對 A 和 B 各做一次差分，用 KMP 查找 A 中有多少個子串為 B 即可。

• 時間復雜度 O(N) 。

Code

#include<cstdio> using namespace std; const int N=1e6+1; int a[N],b[N],next[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int main() {int n=read(),m=read(),ans=0;for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=m;i++) b[i]=read();for(int i=1;i<n;i++) a[i]=a[i+1]-a[i];for(int i=1;i<m;i++) b[i]=b[i+1]-b[i];for(int i=2,j=0;i<m;i++){while(j && b[i]!=b[j+1]) j=next[j];if(b[i]==b[j+1]) j++;next[i]=j;}for(int i=1,j=0;i<n;i++){while(j && a[i]!=b[j+1]) j=next[j];if(a[i]==b[j+1]) j++;if(j==m-1) ans++,j=next[j];}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5437. 【NOIP2017提高A组集训10.31】Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。