Lời giải: Tính hash xâu

Phân tích

Tính hash bằng công thức cộng dồn: \(h_i = (h_{i-1} \cdot B + S[i]) \mod M\). Cách này tương đương với công thức đa thức trong đề bài nhưng hiệu quả hơn vì không cần tính lũy thừa.

Độ phức tạp

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

Code mẫu C++

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

const long long BASE = 31;     // Co so cua hash
const long long MOD = 1e9 + 7; // Modulo de tranh tran so

int main() {
    string s;
    cin >> s;
    long long h = 0;
    // h = (h * BASE + ma_so_ky_tu) % MOD
    for (char c : s) {
        int val = c - 'a' + 1; // 'a' = 1, 'b' = 2, ..., 'z' = 26
        h = (h * BASE + val) % MOD;
    }
    cout << h << endl;
    return 0;
}

Giải thích

• Bắt đầu với h = 0, mỗi lần nhân với BASE rồi cộng giá trị ký tự.
• Phép modulo \(10^9+7\) đảm bảo h không vượt quá phạm vi long long.
• Việc thêm 1 vào giá trị ký tự (c - 'a' + 1) để tránh trường hợp hash("a") = hash("aa") = ... = 0 khi 'a' -> 0.