Submission #2125991

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
using mint = lli;
lli mod = 1e9 + 7;
mint get_hash(string t, mint base)
{
    int n = t.size();
    mint val = 0;
    rep(i, n) val = (val * base + mint(t[i] - 'a') + mod) % mod;
    return val;
}
vector<mint> one_differ(int n, mint base)
{
    mint fuga = 1;
    vector<mint> s;
    rep(j, n)
    {
        for (int i = -25; i <= 25; i++) {
            if (i == 0)
                continue;
            mint piyo = (mint(i) + mod) % mod;
            s.push_back((piyo * fuga) % mod);
        }
        (fuga *= base) %= mod;
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    return s;
}
int main()
{
    string s, t;
    mint base1 = 97, base2 = 103;
    cin >> s >> t;
    int n = t.size();
    string tmp = s.substr(0, n);
    auto th1 = get_hash(t, base1);
    auto th2 = get_hash(t, base2);
    auto sh1 = get_hash(tmp, base1);
    auto sh2 = get_hash(tmp, base2);
    auto s1 = one_differ(n, base1);
    auto s2 = one_differ(n, base2);
    mint v1 = 1, v2 = 1;
    rep(i, n - 1)(v1 *= base1) %= mod, (v2 *= base2) %= mod;
    int cnt = 0;
    for (int i = n; i < s.size() + 1; i++) {
        bool f1 = (*lower_bound(s1.begin(), s1.end(), ((sh1 - th1) % mod + mod) % mod)) == (((sh1 - th1) % mod + mod) % mod);
        bool f2 = (*lower_bound(s2.begin(), s2.end(), ((sh2 - th2) % mod + mod) % mod)) == (((sh2 - th2) % mod + mod) % mod);
        if (f1 and f2)
            cnt++;

        if (i != s.size()) {
            int remove = s[i - n] - 'a';
            int add = s[i] - 'a';
            sh1 = (((sh1 - mint(remove) * v1) * base1 + mint(add) + mod) % mod + mod) % mod;
            sh2 = (((sh2 - mint(remove) * v2) * base2 + mint(add) + mod) % mod + mod) % mod;
        }
    }
    cout << cnt << endl;
}

Submission Info

Judge Result