Hiểu bài toán

Bài toán yêu cầu tìm độ dài của xâu con đối xứng (palindrome) dài nhất trong một xâu S cho trước. Xâu con đối xứng là xâu đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ: 'aba', 'abba'.

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

Cách Quy hoạch động (Dynamic Programming)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen("Doixung.inp","r"))
    {
        freopen ("Doixung.inp","r",stdin);
        freopen ("Doixung.out","w",stdout);
    }

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

    vector<vector<bool>> dp(n, vector<bool>(n, false));

    int ans = 1;

    for (int i = 0; i < n; i++) dp[i][i] = true;

    for (int i = 0; i + 1 < n; i++)
        if (s[i] == s[i + 1])
            dp[i][i + 1] = true, ans = 2;

    for (int k = 3; k <= n; k++) {
        for (int i = 0; i + k - 1 < n; i++) {
            int j = i + k - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                ans = k;
            }
        }
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Cách tiếp cận này sử dụng bảng quy hoạch động dp[i][j] để lưu trữ thông tin xâu con từ chỉ số i đến j có phải là xâu đối xứng hay không.

1. Khởi tạo:

   • dp[i][i] = true: Xâu độ dài 1 luôn đối xứng.
   • Kiểm tra các xâu độ dài 2: Nếu s[i] == s[i+1] thì dp[i][i+1] = true.

2. Quy hoạch:

   • Duyệt độ dài k từ 3 đến n.
   • Với mỗi độ dài, duyệt tất cả các vị trí bắt đầu i.
   • Xâu s[i...j] (với j = i + k - 1) đối xứng nếu:
     • Hai ký tự đầu cuối bằng nhau: s[i] == s[j].
     • Xâu con bên trong s[i+1...j-1] đã được xác định là đối xứng trước đó: dp[i+1][j-1] == true.

3. Kết quả: Luôn cập nhật ans bằng độ dài k khi tìm thấy xâu đối xứng mới.

Cách Mở rộng từ trung tâm (Expand Around Center)

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

int expand(const string &s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("doixung.inp","r",stdin);
    freopen("doixung.out","w",stdout);
    string S;
    cin >> S;
    int n = S.size();

    int res = 1;
    for (int i = 0; i < n; i++) {
        int len1 = expand(S, i, i);       // Palindrome lẻ (có trung tâm là ký tự)
        int len2 = expand(S, i, i + 1);   // Palindrome chẵn (có trung tâm nằm giữa)
        res = max({res, len1, len2});
    }
    cout << res;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Mỗi xâu con đối xứng đều có một "trung tâm". Có 2 loại trung tâm:

1. Trung tâm là một ký tự (ví dụ: ở giữa 'aba').
2. Trung tâm nằm giữa hai ký tự (ví dụ: ở giữa 'abba').

Thuật toán duyệt qua từng vị trí i trong xâu S để xem nó có thể là trung tâm của xâu đối xứng dài bao nhiêu:

• expand(S, i, i): Mở rộng ra hai phía từ vị trí i để tìm xâu đối xứng lẻ.
• expand(S, i, i+1): Mở rộng ra hai phía từ khoảng trống giữa i và i+1 để tìm xâu đối xứng chẵn.

Lưu ý: Độ dài xâu đối xứng được tính bằng right - left - 1 sau khi vòng lặp while dừng lại.

Cách Manacher's Algorithm

// Code mẫu minh họa ý tưởng (giả sử)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string preprocess(string s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    return t;
}

int main() {
    // freopen input/output
    string s; cin >> s;
    string t = preprocess(s);
    int n = t.length();
    vector<int> P(n, 0);
    int C = 0, R = 0;
    for (int i = 0; i < n; i++) {
        int i_mirror = 2 * C - i;
        if (i < R) {
            P[i] = min(R - i, P[i_mirror]);
        }
        while (i + 1 + P[i] < n && i - 1 - P[i] >= 0 && t[i + 1 + P[i]] == t[i - 1 - P[i]]) {
            P[i]++;
        }
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }
    int max_len = 0;
    for (int i = 0; i < n; i++) {
        max_len = max(max_len, P[i]);
    }
    cout << max_len;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Manacher là thuật toán tối ưu để tìm xâu con đối xứng dài nhất trong thời gian tuyến tính O(n).

1. Chuẩn hóa xâu: Chèn ký tự đặc biệt (ví dụ '#') vào giữa các ký tự của xâu gốc để xử lý统一 trường hợp xâu đối xứng chẵn và lẻ. Ví dụ: "aba" -> "#a#b#a#".

2. Sử dụng mảng P: P[i] lưu độ dài nửa bán kính của palindrome tại vị trí i trong xâu đã chuẩn hóa.

3. Duy trì vùng phủ (Range):

   • C: Trung tâm của palindrome dài nhất hiện tại.
   • R: Vị trí bên phải xa nhất của palindrome dài nhất hiện tại.
   • Khi duyệt qua từng ký tự i, ta dùng tính chất đối xứng của palindrome hiện tại để suy ra giá trị ban đầu cho P[i] (tức là sao chép từ P[i_mirror]), sau đó mới mở rộng thêm.

4. Cập nhật C và R khi tìm được palindrome mới có độ dài lớn hơn.

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

Bài học kinh nghiệm

• Bài toán có thể chia làm 2 loại: xâu đối xứng lẻ (trung tâm là ký tự) và xâu đối xứng chẵn (trung tâm nằm giữa 2 ký tự).
• Quy hoạch động cho phép lưu lại kết quả các bài toán con để tránh tính toán lại, nhưng tốn bộ nhớ O(n^2).
• Mở rộng từ trung tâm là cách tiếp cận phổ biến nhất trong thi lập trình thi đấu do cân bằng giữa độ phức tạp thời gian O(n^2) và bộ nhớ O(1).

Lỗi thường gặp

• Xử lý các trường hợp biên: Xâu rỗng, xâu độ dài 1, xâu có tất cả ký tự giống nhau.
• Sai sót trong công thức tính độ dài palindrome: right - left - 1 thay vì right - left + 1.
• Chỉ duyệt loại trung tâm lẻ mà quên trung tâm chẵn (hoặc ngược lại).