Submission #2125983


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(i, 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

Submission Time
Task H - Almost Same Substring
User uenoku
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1994 Byte
Status WA
Exec Time 1869 ms
Memory 127908 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 29
WA × 24
MLE × 6
Set Name Test Cases
All 00-sample1.txt, 100000007.txt, 20-teuchi1.txt, allsame27.txt, allsame28.txt, even.txt, hash-collide.txt, hash-collide2.txt, hash-collide3.txt, hash-collide4.txt, hash-typical.txt, hash-typical2.txt, periodical29.txt, periodical30.txt, periodical31.txt, periodical32.txt, periodical33.txt, periodical34.txt, periodical35.txt, periodical36.txt, periodical37.txt, periodical38.txt, periodical39.txt, periodical40.txt, random00.txt, random01.txt, random02.txt, random03.txt, random04.txt, random05.txt, random06.txt, random07.txt, random08.txt, random09.txt, random10.txt, random11.txt, random12.txt, random13.txt, random14.txt, random15.txt, random16.txt, random17.txt, random18.txt, random19.txt, random20.txt, random21.txt, random22.txt, random23.txt, random24.txt, random25.txt, random26.txt, teuti01.txt, teuti02.txt, teuti03.txt, teuti04.txt, teuti05.txt, teuti06.txt, teuti07.txt, teuti08.txt
Case Name Status Exec Time Memory
00-sample1.txt AC 1 ms 256 KB
100000007.txt AC 2 ms 384 KB
20-teuchi1.txt AC 1 ms 256 KB
allsame27.txt AC 1772 ms 126756 KB
allsame28.txt AC 1186 ms 107636 KB
even.txt AC 3 ms 384 KB
hash-collide.txt AC 6 ms 768 KB
hash-collide2.txt AC 39 ms 2420 KB
hash-collide3.txt AC 47 ms 2548 KB
hash-collide4.txt AC 47 ms 2548 KB
hash-typical.txt AC 27 ms 1528 KB
hash-typical2.txt AC 27 ms 1528 KB
periodical29.txt WA 1772 ms 126116 KB
periodical30.txt WA 1775 ms 126500 KB
periodical31.txt MLE 1778 ms 127652 KB
periodical32.txt MLE 1773 ms 127908 KB
periodical33.txt MLE 1866 ms 127012 KB
periodical34.txt MLE 1868 ms 127140 KB
periodical35.txt MLE 1869 ms 127524 KB
periodical36.txt MLE 1866 ms 127780 KB
periodical37.txt WA 45 ms 900 KB
periodical38.txt WA 45 ms 900 KB
periodical39.txt WA 47 ms 900 KB
periodical40.txt WA 43 ms 900 KB
random00.txt WA 1 ms 256 KB
random01.txt AC 1 ms 256 KB
random02.txt AC 1 ms 256 KB
random03.txt WA 1 ms 256 KB
random04.txt WA 1 ms 256 KB
random05.txt AC 1 ms 256 KB
random06.txt WA 1 ms 256 KB
random07.txt AC 1 ms 256 KB
random08.txt AC 1 ms 256 KB
random09.txt WA 1 ms 256 KB
random10.txt WA 1 ms 256 KB
random11.txt AC 1 ms 256 KB
random12.txt WA 1 ms 256 KB
random13.txt WA 1 ms 256 KB
random14.txt AC 7 ms 896 KB
random15.txt WA 1 ms 256 KB
random16.txt WA 1 ms 256 KB
random17.txt AC 10 ms 1404 KB
random18.txt WA 47 ms 900 KB
random19.txt WA 44 ms 900 KB
random20.txt WA 502 ms 40044 KB
random21.txt WA 45 ms 900 KB
random22.txt WA 46 ms 900 KB
random23.txt WA 1169 ms 103940 KB
random24.txt WA 48 ms 900 KB
random25.txt WA 46 ms 900 KB
random26.txt AC 267 ms 20592 KB
teuti01.txt AC 1 ms 256 KB
teuti02.txt AC 1 ms 256 KB
teuti03.txt AC 1 ms 256 KB
teuti04.txt AC 1 ms 256 KB
teuti05.txt AC 1 ms 256 KB
teuti06.txt AC 1 ms 256 KB
teuti07.txt AC 1 ms 256 KB
teuti08.txt AC 1 ms 256 KB