AOJ 2614: Almost Same Substring

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2614

はい典型って言って書いたらTLEとWAをした。

solution

rolling hash。$O(|S| + |T’| \log |S|)$。 $S$の長さ$|T’|$の部分文字列のrolling hashの一覧を持っておいて、$T’$から$T$の候補を全列挙しそのrolling hashと一致するものを数える。 rolling hashなら途中の文字を変更するのも$O(1)$でできる。

長さ$|T’|$の部分文字列は$|S| - |T| + 1$個、 $T$の候補は$51|T’|$個存在する。 $T$の候補の方が多いため、こちらの一覧を持とうとするとTLEする。

implementation

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

struct rolling_hash_t {
    static constexpr int size = 2; // 16;
    static const int32_t modulo[size];
    array<int32_t, size> data;
};
const int32_t rolling_hash_t::modulo[size] = { 1000000007, 1000000009, }; // 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123, 1000000181, 1000000207, 1000000223, 1000000241, 1000000271, 1000000289, 1000000297 };
bool operator < (rolling_hash_t const & a, rolling_hash_t const & b) {
    return a.data < b.data;
}
rolling_hash_t operator + (rolling_hash_t const & a, rolling_hash_t const & b) {
    rolling_hash_t c;
    repeat (i, rolling_hash_t::size) {
        c.data[i] = a.data[i] + b.data[i];
        if (c.data[i] >= rolling_hash_t::modulo[i]) c.data[i] -= rolling_hash_t::modulo[i];
    }
    return c;
}
rolling_hash_t rolling_hash_from(int a) {
    rolling_hash_t b;
    repeat (i, rolling_hash_t::size) {
        b.data[i] = a % rolling_hash_t::modulo[i];
        if (b.data[i] < 0) b.data[i] += rolling_hash_t::modulo[i];
    }
    return b;
}
rolling_hash_t operator + (rolling_hash_t const & a, int b) {
    return a + rolling_hash_from(b);
}
rolling_hash_t operator - (rolling_hash_t const & a, rolling_hash_t const & b) {
    rolling_hash_t c;
    repeat (i, rolling_hash_t::size) {
        c.data[i] = a.data[i] - b.data[i];
        if (c.data[i] < 0) c.data[i] += rolling_hash_t::modulo[i];
    }
    return c;
}
rolling_hash_t operator * (rolling_hash_t const & a, int b) {
    rolling_hash_t c;
    repeat (i, rolling_hash_t::size) c.data[i] = a.data[i] *(int64_t) b % rolling_hash_t::modulo[i];
    return c;
}
uint64_t to_uint64_t(rolling_hash_t const & a) {
    static_assert (rolling_hash_t::size == 2, "");
    return (uint64_t(a.data[0]) << 32) + a.data[1];
}

int main() {
    // input
    string s, t1; cin >> s >> t1;
    // solve
    int n = t1.size();
    vector<uint64_t> hashes; {
        rolling_hash_t e = {};
        e = e + 1;
        repeat (i, n) {
            e = e * 256;
        }
        rolling_hash_t h = {};
        repeat (i, n) {
            h = h * 256 + s[i];
        }
        hashes.push_back(to_uint64_t(h));
        repeat_from (i, n, s.size()) {
            h = h * 256 - e * s[i-n] + s[i];
            hashes.push_back(to_uint64_t(h));
        }
        whole(sort, hashes);
    }
    int result = 0; {
        rolling_hash_t h = {};
        for (char c : t1) {
            h = h * 256 + c;
        }
        rolling_hash_t e = {};
        e = e + 1;
        repeat_reverse (i, n) {
            char c = t1[i];
            h = h - e * c;
            repeat (j, 52) {
                char d = j < 26 ? 'A' + j : 'a' + j - 26;
                if (d != c) {
                    h = h + e * d;
                    result += whole(upper_bound, hashes, to_uint64_t(h)) - whole(lower_bound, hashes, to_uint64_t(h));
                    h = h - e * d;
                }
            }
            h = h + e * c;
            e = e * 256;
        }
    }
    // output
    cout << result << endl;
    return 0;
}