Editorial for suprefix: Tiền tố và hậu tố

Hiểu bài toán

Cho hai xâu a và b. Tìm xâu c ngắn nhất sao cho a là tiền tố của c và b là hậu tố của c. Điều này có nghĩa là a phải nằm ở đầu c và b phải nằm ở cuối c. Để c có độ dài ngắn nhất, ta cần chồng lấp a và b càng nhiều càng tốt. Cụ thể, ta cần tìm độ dài lớn nhất của một đoạn hậu tố của a trùng với một đoạn tiền tố của b. Gọi độ dài này là k. Khi đó, c sẽ là a nối với phần còn lại của b (tức là b bị thiếu mất k ký tự đầu).

Các cách tiếp cận

Cách Dùng mảng LPS (KMP)

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

vector<int> build_lps(const string &s) {
    int n = s.size();
    vector<int> lps(n, 0);
    for (int i = 1; i < n; i++) {
        int j = lps[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = lps[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        lps[i] = j;
    }
    return lps;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    if (!(cin >> a>>b)) return 0;
    string s=b+"#"+a;
    vector<int> lps=build_lps(s);
    int k=lps[s.size()-1];
    string c = a + b.substr(k);
    cout << c;
    return 0;
}

• Time Complexity: O(|a| + |b|)
• Space Complexity: O(|a| + |b|)

Đây là phương pháp ótimal và hiệu quả nhất.

1. Tạo xâu kết hợp: Tạo một xâu mới s = b + '#' + a. Ký tự đặc biệt # dùng để ngăn cách b và a, đảm bảo rằng độ dài chung tìm được không vượt quá độ dài của b.
2. Xây dựng mảng LPS: Áp dụng thuật toán Knuth-Morris-Pratt (KMP) để xây dựng mảng LPS cho xâu s. Mảng lps[i] lưu độ dài lớn nhất của tiền tố của s đồng thời là hậu tố của s ending tại i.
3. Tìm độ dài chồng lấp: Giá trị lps[s.size() - 1] chính là độ dài lớn nhất của tiền tố của b (vì b nằm ở đầu s) trùng với một hậu tố của a (vì a nằm ở cuối s).
4. Xây dựng kết quả: Xâu c ngắn nhất là a cộng với phần còn lại của b. Phần còn lại này là b bị cắt bỏ k ký tự đầu, tức là b.substr(k). Nối lại ta được c = a + b.substr(k).

Cách Brute Force (Tối ưu)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    int n = a.length();
    int m = b.length();
    int max_overlap = 0;

    // Chỉ kiểm tra các độ dài chồng lấp có thể
    // Độ dài chồng lấp không thể lớn hơn min(n, m)
    int limit = min(n, m);

    for (int k = 1; k <= limit; ++k) {
        // Kiểm tra xem k ký tự cuối của a có trùng với k ký tự đầu của b không
        // a.substr(n - k) so sánh với b.substr(0, k)
        if (a.substr(n - k, k) == b.substr(0, k)) {
            max_overlap = k;
        }
    }

    // Nếu không có chồng lấp (max_overlap = 0), kết quả là a + b
    // Nếu có chồng lấp, a đã chứa phần đầu của b, chỉ cần nối phần còn lại
    cout << a << b.substr(max_overlap) << endl;

    return 0;
}

• Time Complexity: O(min(|a|, |b|)^2)
• Space Complexity: O(|a| + |b|)

Phương pháp này kiểm tra trực tiếp các khả năng chồng lấp.

1. Vòng lặp: Duyệt qua tất cả các độ dài k từ 1 đến độ dài ngắn hơn của a hoặc b.
2. So sánh: Với mỗi k, so sánh trực tiếp k ký tự cuối của a với k ký tự đầu của b.
3. Lưu kết quả: Nếu trùng khớp, cập nhật max_overlap = k. Vì ta duyệt k tăng dần, lần cập nhật cuối cùng sẽ là độ dài lớn nhất.
4. Tạo kết quả: Cuối cùng, nối a với phần đuôi của b (bỏ đi max_overlap ký tự đầu).

Lưu ý: Trong giải pháp này, việc sử dụng substr trong vòng lặp có thể gây tốn bộ nhớ nếu không tối ưu, nhưng về lý thuyết thời gian chạy vẫn cao do số lần so sánh lớn và độ phức tạp của substr (hoặc so sánh trực tiếp từng ký tự).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về tìm độ dài lớn nhất của một hậu tố của a trùng với một tiền tố của b.
• Thuật toán KMP (mảng LPS) được dùng để tìm độ dài lớn nhất của tiền tố của một xâu đồng thời là hậu tố của chính nó. Bằng cách ghép b và a lại (có ký tự ngăn cách), ta利用 được tính chất này để tìm độ dài chồng lấp.
• Ký tự ngăn cách (như #) là quan trọng để đảm bảo độ dài chung tìm được không vượt quá độ dài của b.

Lỗi thường gặp

• Quên sử dụng ký tự ngăn cách khi ghép xâu trong phương pháp KMP có thể dẫn đến việc tìm được độ dài chồng lấp lớn hơn độ dài của b (ví dụ nếu a chứa b hoàn toàn).
• Sử dụng thuật toán Brute Force với độ phức tạp O(N^2) có thể gây TLE (Time Limit Exceeded) với giới hạn 10^5.
• Xử lý sai trường hợp không có chồng lấp (kết quả đúng vẫn là a + b).