\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\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;
}