CF471D MUH and Cube Walls

简要题意

题目传送门

平面上有两堵墙 \(a,b\)。长度分别为 \(n,w\)。求 \(a\) 墙顶端有多少个区间与 \(b\) 墙顶端一样。

\(1\le n,w \le 2 \times 10^5,1 \leq a_i,b_i \leq 10^9\)

代码

先用一下样例的图进行分析：

可以发现，顶端的形状取决于从 \(i\) 到 \(i+1\) 上升或下降了多少格，而不取决于每一个地方的具体高度。自然想到差分数组。

我们求出 \(a,b\) 两堵墙的差分数组后，就可以 \(b\) 为模式串在 \(a\) 上跑 KMP 了。

注意这个做法有一个缺陷，就是在 \(w=1\) 的时候答案是 \(n\)，我们会输出 \(n-1\)。这是因为差分数组比原数组少一个元素导致的。我们特判一下即可。

时间复杂度 \(O(n+w)\)。

代码

这里给出的是传统实现，看不懂题解的拼接两个数组的写法。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int A[1000005],B[1000005];
int fail[1000005];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    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++) A[i]-=A[i+1];
    for(int i=1;i<m;i++) B[i]-=B[i+1];
    n--;m--;
    for(int i=2,j=0;i<=m;i++){
        while(j&&B[i]!=B[j+1]) j=fail[j];
        if(B[j+1]==B[i]) j++;
        fail[i]=j;
    }
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        while(j&&B[j+1]!=A[i]) j=fail[j];
        if(A[i]==B[j+1]) j++;
        if(j==m){ans++;j=fail[j];}
    }
    cout<<ans;
    return 0;
}