~\color{orange}{\text{Hướng dẫn}}~

• Nhận xâu ~T[1 \dots n]~ từ đầu vào. Ta cần tìm một xâu ~S~ thỏa

[1] ~S = T[L\dots R]~ với ~1 \leq L \leq R \leq N~

[2] ~T[i] = T[n - i + 1]\ \ \forall\ \ i = L \dots R~

Trong các xâu thỏa mãn, ta chọn xâu có độ dài lớn nhất (yêu cầu đề)

• Chứng minh

Với ~m~ là một hằng số nào đó

Có ~T_1, T_2, \dots, T_{L-1}~ là ~m~ kí tự được thêm vào trước

Có ~T_n, T_{n-1}, \dots, T_{n - L}~ là ~m~ kí tự được thêm vào sau

Gọi ~P = T[L\dots n - L + 1]~ là xâu trước khi thêm ~m~ kí tự ngẫu nhiên vào trước sau.

Thì từ [1] ta có ~S~ là tiền tố của ~P~ và từ [2] ta có nghịch đảo của ~S~ cũng là hậu tố của ~P~

~\color{goldenrod}{\text{Tiếp cận}}~

• Trâu: Thử các đoạn ~[L \dots R]~

Có tất cả ~O(n^2)~ cách chọn vị trí và ~O(n)~ để thử mỗi lần tổng cộng là ~O(n^3)~

Tối ưu hơn thì khi ta vừa duyệt ta vừa kiểm tra, nếu có một vị trí không thỏa thì cả đoạn không thỏa, bằng cách này chỉ còn ~O(n^2)~

• Chặt nhị phân và hash: Từ mỗi vị trí ~L~ tìm vị trí ~R~ lớn nhất thỏa điều kiện đề

Có ~O(n)~ cách chọn vị trí ~L~

Chặt nhị phân tìm kiếm sẽ mất ~O(log)~

Để kiểm tra 2 đoạn xâu bằng nhau không ta mất ~O(log)~ với tiền xử lí hash

Vậy là ~O(n log^2(n))~ với ~O(n log(MOD))~ tiền xử lí

Có thể tối ưu lên ~O(n log n)~ với ~O(n + log(MOD))~ tiền xử lí

• Hai con trỏ: Trong khi tính chất còn thỏa thì tăng ~R~, ngược lại tăng ~L~

Mỗi lần tăng ~R~ giảm ~L~ ta chỉ cần kiểm tra trong ~O(1)~

Nhận thấy rằng nếu ~R~ không thỏa thì cả đoạn ~[L \dots R]~ không thỏa và ~[P \dots R - 1]~ có độ dài nhỏ hơn ~[L \dots R - 1]~ (~\ \forall\ L \leq P \leq R - 1~) nên ta có thể dịch ~L~ tới ~R + 1 ~ luôn

~\color{green}{\text{Code tham khảo }}~: Hai con trỏ

~^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}~

int query()
{
    string s;
    cin >> s;
    int n = s.size();
    string t(s.rbegin(), s.rend());

    int best_l = 0, best_r = -1;
    for (int l = 0, r = 0; l < n; l = max(l, r) + 1)
    {
        for (r = l - 1; r + 1 < n && s[r + 1] == t[r + 1]; ++r);

        if (best_r - best_l < r - l)
        {
            best_l = l;
            best_r = r;
        }
    }

    cout << s.substr(best_l, best_r - best_l + 1) << '\n';
    return 0;
}