lessons/参考实现/04-KMP与Manacher/CodeForces-471D.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w; cin >> n >> w;
    vector<long long> a(n), b(w);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    if (w == 1) { cout << n << '\n'; return 0; }
    vector<long long> text(n - 1), pattern(w - 1);
    for (int i = 0; i + 1 < n; ++i) text[i] = a[i + 1] - a[i];
    for (int i = 0; i + 1 < w; ++i) pattern[i] = b[i + 1] - b[i];
    vector<int> pi(pattern.size());
    for (int i = 1; i < static_cast<int>(pattern.size()); ++i) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1];
        if (pattern[i] == pattern[j]) ++j;
        pi[i] = j;
    }
    int matched = 0, answer = 0;
    for (long long x : text) {
        while (matched > 0 && x != pattern[matched]) matched = pi[matched - 1];
        if (x == pattern[matched]) ++matched;
        if (matched == static_cast<int>(pattern.size())) {
            ++answer; matched = pi[matched - 1];
        }
    }
    cout << answer << '\n';
}