Hướng giải của Đếm xâu con phân biệt (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: Đếm xâu con phân biệt bằng Suffix Array

Phân tích

Công thức kinh điển: số xâu con phân biệt = \(\sum_i (n - SA[i]) - \sum_i LCP[i]\).

Tại sao?

  • Hậu tố SA[i] có độ dài n - SA[i], mỗi vị trí trong hậu tố này là một tiền tố khác nhau.
  • Nhưng nhiều tiền tố bị trùng giữa các hậu tố liên tiếp, đúng bằng LCP[i].
  • Vậy số tiền tố phân biệt = tổng tất cả tiền tố - trùng lặp.

Độ phức tạp

  • Thời gian: O(N log N) cho SA, O(N) cho LCP
  • Không gian: O(N)

Code mẫu C++

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

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

    // 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 x, int y) {
            if (rank[x] != rank[y]) return rank[x] < rank[y];
            int rx = (x + k < n) ? rank[x + k] : -1;
            int ry = (y + k < n) ? rank[y + k] : -1;
            return rx < ry;
        };
        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;
    }

    // Xay LCP bang Kasai
    vector<int> lcp(n, 0), inv(n);
    for (int i = 0; i < n; i++) inv[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (inv[i] == n - 1) { k = 0; continue; }
        int j = sa[inv[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[inv[i]] = k;
        if (k > 0) k--;
    }

    // Cong thuc: tong (n - SA[i]) - tong LCP[i]
    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += (n - sa[i]) - lcp[i];
    }
    cout << total << endl;
    return 0;
}

Giải thích

  • Mỗi hậu tố sinh ra n - SA[i] xâu con (tất cả các tiền tố của nó).
  • LCP[i] xâu con bị trùng giữa hai hậu tố kề nhau trong SA.
  • Tổng tất cả các tiền tố = \(\sum_i (n - SA[i])\), trừ đi trùng lặp = kết quả.
  • Dùng long long vì tổng có thể lên tới \(10^{10}\) với |S| = 10^5.

Nhận xét

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