471D CF

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpi;
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
const int mod1 = 1e9 + 7, mod2 = 998244353, INF = 2e18, N = 2e5 + 5, L = 19;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// -----------------------------------------------------------------------------
struct Hash
{
    const int MOD = 1e9 + 7;
    const int base1 = 5953; // prime1
    const int base2 = 9733; // prime2
    vpi hashes, pow;
    vi diffs;
    Hash(vi &s)
    {
        int n = s.size();
        hashes.resize(n + 1, {0, 0});
        pow.resize(n + 1, {1, 1});
        for (int i = 1; i < n; i++)
        {
            diffs.pb({s[i] - s[i - 1]});
        }
        n = diffs.size();
        for (int i = 0; i < n; i++)
        {
            int value = (diffs[i] % MOD) + MOD;
            hashes[i + 1].first = (hashes[i].first * base1 + value) % MOD;
            hashes[i + 1].second = (hashes[i].second * base2 + value) % MOD;
            pow[i + 1].first = (pow[i].first * base1) % MOD;
            pow[i + 1].second = (pow[i].second * base2) % MOD;
        }
    }
    pair<int, int> gethash(int l, int r)
    {
        l++, r++;
        int hash1 = (hashes[r].first - (1LL * hashes[l - 1].first * pow[r - l + 1].first) % MOD + MOD) % MOD;
        int hash2 = (hashes[r].second - (1LL * hashes[l - 1].second * pow[r - l + 1].second) % MOD + MOD) % MOD;
        return {hash1, hash2};
    }
    // Hash ht(t) // auto it = ht.gethash(l,r)
};
void solve()
{
    int n, m;
    cin >> n >> m;
    vi a(n), b(m);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
    }
    if (m == 1)
    {
        cout << n << endl;
        return;
    }
    if (m > n)
    {
        cout << 0 << endl;
        return;
    }
    Hash a1(a), b1(b);
    // hash the differences
    auto check = b1.gethash(0, m - 2);
    int ans = 0;
    for (int i = 0; (i + m - 2) <= n; i++)
    {
        if ((a1.gethash(i, i + m - 2)) == check)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    // __START__;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    // __END__;
    return 0;
}