String Hashing (phần 2) - LQDOJ: Le Quy Don Online Judge

A5K42 @ Tân Khoa

CONTEST PHẦN HAI

Tài liệu tham khảo:

https://wiki.vnoi.info/algo/string/hash#/

Solution (cũ):
https://hackmd.io/@zipdang04/tk22a5hash/edit
https://hackmd.io/@zipdang04/22a5kmp/edit

Lý thuyết

Kiến thức cơ bản về Hash (tác giả: zipdang04)

Kudos to the author

Mã hash của một xâu (1-index)

\(hash(s)=s[1] \cdot base^{n-1}+s[2] \cdot base^{n-2} + ... + s[n-1] \cdot base + s[n] \ (mod \ m) = \sum_{i=1}^{n} s[i] \cdot base^{n-i} (mod \ m)\) .

Nếu \(hash(s) = hash(t)\) thì ngầm định hiểu \(s = t\).

Lưu ý nên chọn \(base\) là một số nguyên tố lớn hơn \(255\), \(m\) là một số nguyên tố lớn hơn \(10^9\).

Mã hash tiền tố

\(hash(s[1...i])= \sum_{j=1}^{i} s[j] \cdot base^{i-j} \ (mod \ m)\) .

\(hash(s[1...i]) = hash(s[1...i-1]) * base + s[i] \ (mod \ m)\).

Mã hash của đoạn con liên tiếp

\(hash(s[i...j]) = s[i] \cdot base^{j-i}+s[i+1] \cdot base^{j-i-1} + ... + s[j] \ (mod \ m) = \sum_{k=i}^{j} s[k] \cdot base^{j-k} (mod \ m)\).

\(=\sum_{k=1}^{j} s[k] \cdot base^{j-k} - \sum_{k=1}^{i-1} s[k] \cdot base^{j-k} \ (mod \ m) = hash(s[1...j]) - hash(s[1..i-1]) \cdot base^{j-i+1} \ (mod \ m)\).

Ứng dụng

SPOILER ALERT

Code chi tiết từng bài:

PERIOD - Tìm chu kỳ

Brute Force + Hash

C++

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

#define int long long
const int BASE = 12232001;
const int MOD = 1e9 + 7;

string s;
int n;
vector<int> prefixHash, basePow;

void buildHash() {
    prefixHash.resize(n + 1);
    basePow.resize(n + 1);
    basePow[0] = 1;
    for (int i = 1; i <= n; i++) {
        prefixHash[i] = (prefixHash[i - 1] * BASE + s[i]) % MOD;
        basePow[i] = basePow[i - 1] * BASE % MOD;
    }
}

int getHash(int i, int j) {
    return (prefixHash[j] - prefixHash[i - 1] * basePow[j - i + 1] % MOD + MOD) % MOD;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    n = s.size();
    s = "#" + s;
    buildHash();

    for (int T = 1; T <= n; T++) {
        bool isPeriod = true;
        for (int i = 1; i <= n; i += T) {
            int j = min(i + T - 1, n);
            if (getHash(i, j) != getHash(1, j - i + 1)) {
                isPeriod = false;
                break;
            }
        }
        if (isPeriod) cout << T << " ";
    }
}

PUN - Xâu con lặp

Binary search + Double/Triple Hash

C++

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
const int MOD = 1e9 + 7;

const int BASE = 12232001; // thang 12 ngay 23 nam 2001
vi hash_MODs = {MOD, MOD + 2, MOD + 26};
int hash_MOD;
vi pref_hash, BASE_pow;

int n;
string s;

void input() {
    cin >> n >> s;
    s = "#" + s;
    pref_hash.resize(n + 1);
    BASE_pow.resize(n + 1);
    BASE_pow[0] = 1;
}

void build_hash() {
    assert(hash_MOD != 0);
    for (int i = 1; i <= n; i++) {
        BASE_pow[i] = BASE_pow[i - 1] * BASE % hash_MOD;
        pref_hash[i] = (pref_hash[i - 1] * BASE + s[i] - 'a') % hash_MOD;
    }
}

int get_hash(int l, int r) {
    assert(l <= r);
    return (pref_hash[r] - pref_hash[l - 1] * BASE_pow[r - l + 1] % hash_MOD + hash_MOD) 
    % hash_MOD;
}

bool isChecked(int leng) {
    map<int, int> mp;
    for (int l = 1; l + leng - 1 <= n; l++) {
        int r = l + leng - 1;
        int hash_code = get_hash(l, r);
        if (!mp.count(hash_code)) mp[hash_code] = l;
        else if (mp[hash_code] + leng <= l) return true;
    }
    return false;
}

void solve() {
    int ans = n;
    for (int i: hash_MODs) {
        hash_MOD = i;
        build_hash();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (isChecked(mid)) l = mid; else r = mid - 1;
        }
        ans = min(ans, l);
    }
    cout << ans << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    input();
    solve();
}

VOSTR - Xử lý xâu

Binary search + Hash + Alphabetically

C++

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>

const int MOD = 1e9 + 7;
const int base = 12232001; 

int n, m;
string s, t;
vector<int> hash_s, hash_t, base_p;

void buildhash() {
    hash_s.resize(n + 1);
    hash_t.resize(m + 1);
    base_p.resize(max(n, m) + 1);
    for (int i = 1; i <= n; i++) 
        hash_s[i] = (hash_s[i - 1] * base + s[i - 1]) % MOD;
    for (int i = 1; i <= m; i++)
        hash_t[i] = (hash_t[i - 1] * base + t[i - 1]) % MOD;
    base_p[0] = 1;
    for (int i = 1; i < base_p.size(); i++)
        base_p[i] = base_p[i - 1] * base % MOD;
}

int getHash(const vector<int>& v, int i, int j) {
    return (v[j] - v[i - 1] * base_p[j - i + 1] % MOD + MOD) % MOD;
}

void solve(int l, int r, int u, int v) {
    int left = 1, right = min(r - l, v - u) + 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (getHash(hash_s, l, l + mid - 1) == getHash(hash_t, u, u + mid - 1))
            left = mid + 1;
        else
            right = mid;
    }

    if (s[l + left - 2] == t[u + left - 2]) {
        if (r - l == v - u)
            cout << "=";
        else if (r - l > v - u)
            cout << ">";
        else
            cout << "<";
    }
    else if (s[l + left - 2] < t[u + left - 2])
        cout << "<";
    else cout << ">";
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> s >> t;
    buildhash();
    int q;
    cin >> q;
    while (q--){
        int l, r, u, v;
        cin >> l >> r >> u >> v;
        solve(l, r, u, v);
    }

}

twoopers - Thao tác trên chuỗi

Count + Greedy + Hash

C++

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

#define int long long

const int base = 12232001;
const int MOD = 1e9 + 9;

int n, m;
string s, t;
vector<int> hashS, hashT, basePow;
map<int, int> mp;
vector<int> cntS(300), cntT(300);

void buildHash() {
    n = s.size(),
    m = t.size();
    s = "#" + s;
    t = "#" + t;
    hashS.resize(n + 1);
    hashT.resize(m + 1);
    basePow.push_back(1);
    for (int i = 1; i <= n; i++) {
        hashS[i] = (hashS[i - 1] * base + s[i]) % MOD;
    }
    for (int i = 1; i <= m; i++) {
        hashT[i] = (hashT[i - 1] * base + t[i]) % MOD;
    }
    for (int i = 1; i <= n || i <= m; i++) {
        basePow.push_back(basePow.back() * base % MOD);
    }
}

int getHashT(int l, int r) {
    return (hashT[r] - hashT[l - 1] * basePow[r - l + 1] % MOD + MOD) % MOD;
}

int changeS(int vt, char c) {
    return (hashS[n] + (c - s[vt] + MOD) % MOD * basePow[n - vt] % MOD) % MOD;
}

void quayT() {
    for (int i = 1; i <= m; i++) {
        int newhash =(getHashT(i + 1, m) * basePow[i] + hashT[i]) % MOD;
        mp[newhash] += 1;
    }
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s >> t;
    buildHash();
    quayT();
    for (int i = 1; i <= n; i++) {
        cntS[s[i]]++;
        cntT[t[i]]++;
    }
    int ans = 0;
    char k = '#';
    for (int i = 'A'; i <= 'Z'; i++)
        if (cntS[i] == cntT[i] - 1) k = i;
    for (int i = 1; i <= n; i++) {
        if (cntS[s[i]] == cntT[s[i]])
            ans += mp[changeS(i, s[i])];
        if (cntS[s[i]] == cntT[s[i]] + 1)
            ans += mp[changeS(i, k)];
    }
    cout << ans;
}

Bình luận

Tải bình luận...

Không có bình luận nào.