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. Độ dài |S| có thể lên tới 50,000, đòi hỏi thuật toán hiệu quả.

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

Cách Mở rộng từ tâm (Manacher-like)

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

int main() {
    string s; cin >> s;
    int n = s.size(), res = 1;
    for(int i = 0; i < n; i++){
        // Palindrome lẻ (tâm là s[i])
        for(int l=i, r=i; l>=0 && r<n && s[l]==s[r]; res=max(res,r-l+1), l--, r++);
        // Palindrome chẵn (khe giữa s[i] và s[i+1])
        for(int l=i, r=i+1; l>=0 && r<n && s[l]==s[r]; res=max(res,r-l+1), l--, r++);
    }
    cout << res;
}

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

Thuật toán này duyệt qua từng ký tự trong xâu coi nó là tâm của một xâu đối xứng. Với mỗi tâm, nó mở rộng sang hai phía trái và phải chừng nào các ký tự còn giống nhau. Có hai loại đối xứng: loại lẻ (có tâm là một ký tự,ví dụ 'aba') và loại chẵn (có tâm là khe giữa hai ký tự, ví dụ 'abba'). Độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất (xâu toàn cùng một ký tự), nhưng với n=50,000 thì có thể bị TLE. Tuy nhiên, đây là cách tiếp cận trực quan nhất.

Cách Manacher Algorithm (Tối ưu)

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

using namespace std;

string preprocess(const string &s) {
    if (s.empty()) return "^#";
    string res = "^";
    for (char c : s) {
        res += '#';
        res += c;
    }
    res += '#';
    res += '$';
    return res;
}

int solve(const string &s) {
    string T = preprocess(s);
    int n = T.length();
    vector<int> P(n, 0);
    int center = 0, right = 0;
    int maxLen = 0;

    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * center - i;

        if (right > i) {
            P[i] = min(right - i, P[i_mirror]);
        } else {
            P[i] = 0;
        }

        while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
            P[i]++;
        }

        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }

        if (P[i] > maxLen) {
            maxLen = P[i];
        }
    }
    return maxLen;
}

int main() {
    string s;
    if (getline(cin, s)) {
        cout << solve(s) << endl;
    }
    return 0;
}

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

Thuật toán Manacher giải quyết bài toán trong thời gian tuyến tính O(n). Nó tận dụng tính chất đối xứng của các xâu con đối xứng đã tính toán trước đó để tránh lặp lại các phép so sánh. Xâu ban đầu được chuyển đổi (preprocess) thành xâu có độ dài lẻ bằng cách chèn ký tự đặc biệt giữa các ký tự (ví dụ 'aba' -> '#a#b#a#'), giúp xử lý统一 cả đối xứng chẵn và lẻ. Mảng P lưu độ dài nửa bán kính đối xứng tại mỗi vị trí. Khi duyệt, nếu vị trí hiện tại nằm trong khoảng đối xứng của một trung tâm trước đó, ta khởi tạo P[i] dựa trên P của đối xứng tương ứng (i_mirror). Sau đó tiếp tục mở rộng.

Cách Manacher (Code ngắn)

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

int main() {
    string s, t = "^";
    if (getline(cin, s)) {
        for (char c : s) t += string(1, c) + "#";
        t.back() = '$';
        int n = t.length();
        vector<int> p(n);
        int l = 0, r = 0;
        for (int i = 1; i < n - 1; i++) {
            p[i] = (r > i) ? min(r - i, p[l + r - i]) : 0;
            while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) p[i]++;
            if (i + p[i] > r) { l = i - p[i]; r = i + p[i]; }
        }
        cout << *max_element(p.begin(), p.end());
    }
}

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

Đây là biến thể khác của thuật toán Manacher, sử dụng biến l và r để duy trì khoảng cách đối xứng xa nhất về bên phải. Mảng p[i] lưu độ dài của xâu con đối xứng có tâm tại i. Tuy nhiên, trong code này, t được tạo bằng cách thêm '#' xen kẽ, nên giá trị p[i] thực tế chính là độ dài xâu con đối xứng trong xâu gốc. Ví dụ: t = ^#a#b#a#, tại i=4 (ký tự 'b'), p[4]=3, tương ứng với độ dài 'aba' là 3. Nếu ta muốn tính 'abba', t sẽ là ^#a#b#b#a#, tại trung tâm '#' giữa 'b' và 'b', p[i]=4, tương ứng 'abba' độ dài 4. Do đó, kết quả là giá trị lớn nhất của mảng p.

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

Bài học kinh nghiệm

• Mọi xâu con đối xứng đều có thể được xác định bởi một trung tâm (hoặc một ký tự đối xứng lẻ, hoặc một khe giữa hai ký tự đối xứng chẵn).
• Thuật toán Manacher dựa trên ý tưởng duy trì một khoảng đối xứng (center, right) và tận dụng các giá trị tính toán trước (thông qua đối xứng gương) để giảm số lần so sánh. Điều này đảm bảo mỗi ký tự chỉ được xử lý một số lần cố định, đạt độ phức tạp O(n).
• Việc chuẩn hóa xâu (chèn ký tự đặc biệt giữa các ký tự) giúp loại bỏ sự phân biệt giữa xâu đối xứng lẻ và chẵn, đơn giản hóa việc mã hóa.

Lỗi thường gặp

• Quên kiểm tra các trường hợp biên như xâu rỗng, xâu độ dài 1.
• Sai chỉ số trong thuật toán Manacher khi truy cập mảng hoặc chuỗi chuẩn hóa, dẫn đến truy cập ngoài vùng nhớ hoặc tính toán sai độ dài.
• Trong giải pháp bằng cách mở rộng tâm (Solution 1 và 2), nếu không tối ưu và input lớn (ví dụ 50,000 ký tự giống nhau), chương trình sẽ bị TLE do O(n^2).