Hướng giải của LCP và truy vấn trên Suffix Array

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: LCP trên Suffix Array

Phân tích

Sau khi xây dựng Suffix Array bằng doubling, xây dựng mảng LCP bằng thuật toán Kasai O(N). Sau đó, với mỗi truy vấn (i, j), dùng Sparse Table (RMQ) để trả lời trong O(1).

Độ phức tạp

  • Thời gian: O(N log N) để build + O(1) cho mỗi truy vấn
  • Không gian: O(N log N)

Code mẫu C++

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

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

    // Buoc 1: Xay dung Suffix Array (doubling)
    vector<int> sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int a, int b) {
            if (rank[a] != rank[b]) return rank[a] < rank[b];
            int ra = (a + k < n) ? rank[a + k] : -1;
            int rb = (b + k < n) ? rank[b + k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
        }
        rank = tmp;
    }

    // Buoc 2: Xay dung LCP bang Kasai (O(N))
    vector<int> lcp(n, 0), inv(n);
    for (int i = 0; i < n; i++) inv[sa[i]] = i;  // sa[i] dung thu i trong SA

    int k = 0;
    for (int i = 0; i < n; i++) {
        if (inv[i] == n - 1) { k = 0; continue; }  // Hau to cuoi khong co LCP
        int j = sa[inv[i] + 1];  // Hau to dung ngay sau trong SA
        // So sanh S[i+k] va S[j+k] cho den khi khac nhau
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[inv[i]] = k;
        if (k > 0) k--;
    }

    // Buoc 3: Sparse Table cho RMQ
    vector<vector<int>> st(n, vector<int>(20));
    for (int i = 0; i < n; i++) st[i][0] = lcp[i];
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    auto query = [&](int l, int r) {
        if (l > r) swap(l, r);
        if (l == r) return n - sa[l];  // Cung mot hau to
        r--;
        int k = 31 - __builtin_clz(r - l + 1);
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    };

    int qi, qj;
    cin >> qi >> qj;
    cout << query(qi, qj) << endl;
    return 0;
}

Giải thích

  • Kasai dùng tính chất: khi chuyển từ vị trí i sang i+1, LCP chỉ giảm nhiều nhất 1.
  • Sparse Table chuẩn bị sẵn câu trả lời cho mọi đoạn [l, r], cần tính min trên LCP.
  • Lưu ý: lcp[k] lưu độ dài khớp giữa SA[k] và SA[k+1], nên truy vấn RMQ phải trên nửa khoảng.

Nhận xét

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