Codeforces Round #269 (Div. 2)（D. MUH and Cube Walls（KMP））

題目連結：點選打開連結

題意：給你一個長度為n的序列， 讓你找其中有幾個長度為m的序列的形狀（即高低差距）

思路：将數組預處理成相鄰兩數的差的形式， 然後KMP即可。 KMP的精華在于狀态轉移圖的構造， 有點DP的思想， 也就是預處理失配之後能轉移到代價盡量小的地方。

這裡附上一篇KMP詳解：點選打開連結

細節參見代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 200000 + 10;
int n,m,ans=0,f[maxn],T[maxn],p[maxn],a[maxn];
void getfail() {
    f[0] = 0; f[1] = 0;
    for(int i=1;i<m;i++) {
        int j = f[i];
        while(j && p[i] != p[j]) j = f[j];
        f[i+1] = p[i] == p[j] ? j+1 : 0;
    }
}
void _find() {
    getfail();
    int j = 0;
    for(int i=0;i<n;i++) {
        while(j && p[j] != T[i]) j = f[j];
        if(p[j] == T[i]) j++;
        if(j >= m) ++ans, j = f[j];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++) {
        if(i > 0) T[i] = a[i] - a[i-1];
        else T[i] = INF;
    }
    for(int i=0;i<m;i++) {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++) {
        if(i == 0) ;
        else p[i-1] = a[i] - a[i-1];
    }
    ans = 0;
    --m;
    _find();
    printf("%d\n",ans);
    return 0;
}