#include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, w; cin >> n >> w; vector 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 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 pi(pattern.size()); for (int i = 1; i < static_cast(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(pattern.size())) { ++answer; matched = pi[matched - 1]; } } cout << answer << '\n'; }