Hướng giải của Xâu con chung dài nhấ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: Xâu con chung dài nhất (Suffix Array)

Phân tích

Ghép S = A + "#" + B rồi xây dựng Suffix Array và LCP. Khi duyệt qua mảng LCP, ta tìm giá trị LCP lớn nhất giữa hai hậu tố thuộc hai xâu khác nhau.

Độ phức tạp

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

Code mẫu C++

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

int main() {
    string a, b;
    cin >> a >> b;

    // Ghep A + '#' + B voi '#' la ky tu phan tach
    string s = a + "#" + b;
    int n = s.size(), na = a.size();

    // Xay dung SA
    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 dung 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--;
    }

    // Tim LCP lon nhat giua hai hau to thuoc hai xau khac nhau
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        // sa[i] < na: thuoc xau A; sa[i] >= na + 1: thuoc xau B
        bool diffString = (sa[i] < na) != (sa[i + 1] < na);
        if (diffString) {
            ans = max(ans, lcp[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

Giải thích

  • Ký tự # (có thể chọn bất kỳ không xuất hiện trong A, B) đánh dấu ranh giới.
  • sa[i] < na nghĩa là hậu tố đó thuộc xâu A. Ngược lại sa[i + 1] >= na + 1 thuộc xâu B.
  • Chỉ quan tâm cặp hậu tố thuộc hai xâu khác nhau, vì LCP giữa hai hậu tố cùng xâu không tính.

Nhận xét

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