Hướng giải của Palindrome với Hash

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Palindrome với Hash (Hash xuôi và Hash ngược)

Phân tích

Xâu con S[l..r] là palindrome khi và chỉ khi nó bằng với xâu đảo ngược của nó. Tính hash xuôi của S và hash "ngược" của S (hash của S đảo ngược). Xâu con S[l..r] palindrome nếu hash xuôi bằng hash của xâu con ngược.

Độ phức tạp

  • Thời gian: O(N + Q)
  • Không gian: O(N)

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

const long long BASE = 31;
const long long MOD = 1e9 + 7;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    // Dao nguoc xau S de tinh hash "nguoc"
    string rs = s;
    reverse(rs.begin(), rs.end());

    // Tinh mang luy thua chung
    vector<long long> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * BASE % MOD;

    // Hash tien to cua S (xuoi) va cua rs (nguoc)
    vector<long long> hf(n + 1), hb(n + 1);
    for (int i = 0; i < n; i++) {
        hf[i + 1] = (hf[i] * BASE + (s[i] - 'a' + 1)) % MOD;   // Hash xuoi
        hb[i + 1] = (hb[i] * BASE + (rs[i] - 'a' + 1)) % MOD;  // Hash nguoc
    }

    // Ham lay hash cua doan [l, r] tu mang hash h
    auto getHash = [&](vector<long long>& h, int l, int r) {
        return (h[r + 1] - h[l] * pw[r - l + 1] % MOD + MOD) % MOD;
    };

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // Hash xuoi cua S[l..r]
        long long f = getHash(hf, l, r);
        // Hash nguoc cua S[l..r] = hash cua rs[n-1-r..n-1-l]
        long long b = getHash(hb, n - 1 - r, n - 1 - l);
        cout << (f == b ? "YES" : "NO") << endl;
    }
    return 0;
}

Giải thích

  • Xâu S[l..r] khi đảo ngược trở thành S[r]S[r-1]...S[l], tương ứng với xâu rs[n-1-r..n-1-l].
  • Nếu hash xuôi = hash của xâu đảo thì xâu đó đọc xuôi = đọc ngược, tức là palindrome.
  • Mỗi truy vấn trả lời trong O(1) nhờ hash tiền tố.

Nhận xét

Không có ý kiến tại thời điểm này.