AOJ 2614: Almost Same Substring
はい典型って言って書いたら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;
}