Hướng giải của Ghép xâu tối ưu bằng KMP

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: Ghép hai xâu siêu xâu tối thiểu

Phân tích

Ghép tối ưu: A ở trước, B ở sau. Phần "chồng lấn" là đoạn hậu tố dài nhất của A đồng thời là tiền tố dài nhất của B. Tính bằng prefix function trên xâu B + "#" + A.

Độ phức tạp

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

Code mẫu C++

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

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

    // Xau ghep: B + '#' + A
    // Can tinh pi tren xau nay de tim do dai cua phan hau to A trung voi tien to B
    string s = b + "#" + a;
    int n = s.size();

    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }

    // Phan chong lan toi da = pi[n-1]
    int overlap = pi[n - 1];
    // Tong do dai hai xau tru di phan chong lan
    cout << (int)a.size() + (int)b.size() - overlap << endl;
    return 0;
}

Giải thích

  • Tại sao ghép B + "#" + A? Vì ta muốn tìm xâu con của A ở phía cuối mà trùng với xâu con của B ở phía đầu.
  • Ký tự # ngăn không cho khớp "xuyên" từ phần A sang phần B ngược.
  • overlap = π[n-1] là độ dài phần chồng lấn lớn nhất.
  • Có hai cách ghép (A+B hoặc B+A); bài này giả sử yêu cầu A trước B sau.

Nhận xét

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