Submission #2135624

---

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, base = 97;
int main()
{
    string s, t;
    cin >> s >> t;
    lli v = 0, e = 1;
    rep(i, t.size())
    {
        v = v * base + s[i] - 'a';
        v %= mod;
    }
    rep(i, t.size() - 1)(e *= base) %= mod;
    map<int, int> st;
    for (lli i = t.size(); i < s.size() + 1; i++) {
        st[v]++;
        //    st.insert(v);
        //cout << v << endl;
        if (i == s.size())
            break;
        v = base * (v - e * lli(s[i - t.size()] - 'a')) + lli(s[i] - 'a');
        ((v %= mod) += mod) %= mod;
    }
    v = 0;
    rep(i, t.size())
    {
        v = v * base + t[i] - 'a';
        v %= mod;
    }
    e = 1;
    lli cnt = 0;
    rrep(j, t.size())
    {
        for (lli i = 0; i < 26; i++) {
            if (i == t[j] - 'a')
                continue;
            lli nx = ((v - lli(t[j] - 'a') * e + e * i) % mod + mod) % mod;
            cnt += st[nx];
        }
        (e *= base) %= mod;
    }
    cout << cnt << endl;
}

Submission Info

Judge Result