Xâu Đối Xứng (XDXUNG) (HSG12 Lâm Đồng 2025 – Bài 3)

Nguồn: Đề thi HSG Tin học 12 tỉnh Lâm Đồng 2025 (Bài 3) Độ khó: Khá Xâu Manacher Loang từ tâm

Đề bài

Câu 3: Xâu đối xứng (4.0 điểm) – dữ liệu vào XDXUNG.INP, kết quả XDXUNG.OUT.

Cho một xâu $S$ (tối đa $10^6$ kí tự).

Xâu con của xâu $S$ là một dãy các kí tự liên tiếp nhau trong $S$.

Xâu đối xứng là xâu đọc từ trái qua phải hay đọc từ phải qua trái đều giống nhau, chẳng hạn như các xâu ‘a’, ‘abba’, ‘abcdcba’...

Yêu cầu: Tìm số nguyên $K$ là độ dài của xâu con đối xứng dài nhất trong xâu $S$.

Input: Trong file XDXUNG.INP

• Một xâu $S$.

Output: Ghi kết quả vào file XDXUNG.OUT

• Một số nguyên $K$: là độ dài của xâu con đối xứng dài nhất của xâu $S$.

(Code trong bài đọc/ghi chuẩn – bàn phím/màn hình; khi đi thi đọc ghi file thì các bạn thêm freopen nhé, không là 0 điểm đó.)

XDXUNG.INP – ví dụ 1

Abcbcadk %

XDXUNG.OUT

3

XDXUNG.INP – ví dụ 2

abcccccbbbbdddkh

XDXUNG.OUT

7

Lời mở đầu

Bài này là bài 3 trong đề thi học sinh giỏi Tin học lớp 12 tỉnh Lâm Đồng năm 2025. Đây là một bài toán khá cổ điển: tìm xâu con đối xứng (palindrome) dài nhất. Với xâu dài tới $10^6$ kí tự thì cách "loang từ tâm" quen thuộc sẽ không kịp, ta cần tới thuật toán Manacher. Mình viết lời giải + code chi tiết, hi vọng mang đến giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ:

• Abcbcadk %: xâu con đối xứng dài nhất là bcb (hoặc cbc), dài $3$. Để ý xâu có cả dấu cách và kí tự %, nên phải đọc nguyên cả dòng (getline) chứ không đọc bằng cin >> được. Ngoài ra A hoa và a thường là hai kí tự khác nhau.
• abcccccbbbbdddkh: xâu con dài nhất là bcccccb, dài $7$ (dài hơn ccccc hay bbbb).

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Loang từ tâm · O(N²)Cách 2Manacher · O(N)

Cách 1Loang từ tâm – O(N²)

Mỗi xâu đối xứng đều có một tâm: xâu độ dài lẻ (như bcb) có tâm là 1 kí tự, xâu độ dài chẵn (như abba) có tâm nằm giữa 2 kí tự. Vậy ta thử từng tâm, rồi "loang" ra hai bên với hai con trỏ $l$, $r$: chừng nào $t_l = t_r$ thì còn đối xứng, $l$ lùi trái, $r$ tiến phải. Khi dừng, đoạn đối xứng là $(l, r)$ không kể hai đầu, dài $r - l - 1$.

Với mỗi vị trí $c$ ta loang 2 lần: tâm lẻ ($l = r = c$) và tâm chẵn ($l = c$, $r = c + 1$).

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    string t;
    getline(cin, t);
    if (!t.empty() && t.back() == '\r') t.pop_back();
    int m = t.size(), res = 0;
    for (int c = 0; c < m; c ++){
        int l = c, r = c;
        while (l >= 0 && r < m && t[l] == t[r]){ l --; r ++; }
        res = max(res, r - l - 1);
        l = c; r = c + 1;
        while (l >= 0 && r < m && t[l] == t[r]){ l --; r ++; }
        res = max(res, r - l - 1);
    }
    cout << res << endl;
}

import sys

t = sys.stdin.readline().rstrip('\n').rstrip('\r')
m = len(t)
res = 0
for c in range(m):
    l, r = c, c
    while l >= 0 and r < m and t[l] == t[r]:
        l -= 1
        r += 1
    res = max(res, r - l - 1)
    l, r = c, c + 1
    while l >= 0 and r < m and t[l] == t[r]:
        l -= 1
        r += 1
    res = max(res, r - l - 1)
print(res)

Không gian$O(N)$

Thời gian$O(N^2)$

TLE với xâu kiểu "aaaa...a"

Xâu ngẫu nhiên thì cách này chạy rất nhanh vì loang được vài bước là gặp kí tự khác. Nhưng với xâu toàn chữ a dài $10^6$, tâm nào cũng loang tới tận mép xâu ⇒ cỡ $\frac{N^2}{2} = 5 \cdot 10^{11}$ phép so sánh. Mình chạy thử bản C++ hơn 20 giây vẫn chưa xong ⇒ chắc chắn TLE.

Cách 2Thuật toán Manacher – O(N)

Bài này có thể dễ dàng được giải bằng Manacher. Tuy nhiên vì xét cả hai trường hợp tâm chẵn, tâm lẻ khá là mệt, nên ở giữa hai kí tự bất kỳ trong $S$, ta sẽ chèn thêm một kí tự ảo (mình dùng #). Nhận xét rằng trường hợp palin chẵn trong xâu ban đầu thì ở xâu mới (xâu sau khi chèn thêm kí tự ảo) sẽ có độ dài lẻ và tâm là kí tự ảo đó. Ví dụ abba → a#b#b#a: palin chẵn abba trở thành palin lẻ tâm là dấu # ở giữa. Như vậy ta chỉ cần xử lý palin lẻ trên xâu mới.

Mảng cnt

Với xâu mới $s$ (đánh số từ $1$, độ dài $n = 2|S| - 1$), $cnt[i]$ là số bước loang được từ tâm $i$, tính cả chính nó: $s[i - k] = s[i + k]$ với mọi $0 \le k \lt cnt[i]$. Bán kính palin quanh $i$ là $a = cnt[i] - 1$.

Nếu tính $cnt[i]$ bằng cách loang như cách 1 thì vẫn $O(N^2)$. Mẹo của Manacher là tận dụng đối xứng gương: luôn giữ đoạn palin $(l, r)$ (không tính hai đầu) có mép phải $r$ xa nhất đã tìm được. Khi xét tâm $i$ nằm trong đoạn đó, điểm đối xứng của $i$ qua tâm đoạn là $j = l + r - i$ (đã tính rồi). Vì đoạn $(l, r)$ đối xứng nên quanh $i$ "giống y" quanh $j$, ít nhất là trong phạm vi còn nằm trong đoạn:

$cnt[i] \ge \min(r - i,\ cnt[l + r - i])$

Ta khởi tạo $cnt[i]$ bằng giá trị đó (hoặc $0$ nếu $i$ nằm ngoài đoạn), rồi mới loang tiếp. Mỗi lần loang thêm thành công thì mép phải $r$ được đẩy ra xa hơn, mà $r$ chỉ tăng chứ không giảm, nên tổng số lần loang của cả thuật toán chỉ $O(n)$. Hai kí tự canh biên . và ^ ở hai đầu giúp vòng while tự dừng mà không cần kiểm tra chỉ số.

Đổi bán kính ra độ dài thật. Ta có thể dễ dàng tính được độ dài của đoạn palin trên xâu mới và số kí tự ảo trong đó để trừ đi. Đoạn palin quanh tâm $i$ là $[i - a,\ i + a]$; trong xâu mới kí tự thật nằm ở vị trí lẻ, kí tự ảo ở vị trí chẵn, nên:

• Tâm $i$ là kí tự thật ($i$ lẻ): số kí tự thật trong đoạn là $2\lfloor a/2 \rfloor + 1$.
• Tâm $i$ là kí tự ảo ($i$ chẵn): số kí tự thật trong đoạn là $2\lceil a/2 \rceil = 2\lfloor (a+1)/2 \rfloor$.

Xâu đề có chứa sẵn dấu # thì sao?

Không sao cả! Khi so $s[i - k]$ với $s[i + k]$, hai vị trí luôn cùng tính chẵn lẻ, nên kí tự thật chỉ so với kí tự thật, kí tự ảo chỉ so với kí tự ảo. Cũng vì vậy mà ở bước cuối mình phân biệt thật/ảo bằng chẵn lẻ của $i$ chứ không so s[i] == '#'.

Đọc thêm về thuật toán này tại: wiki.vnoi.info/algo/string/manacher.

Minh hoạ Manacher trên xâu đã chèn kí tự ảo

Em nhập xâu (tối đa 16 kí tự) rồi bấm Tiếp. Mỗi tâm $i$ có 2 bước: lấy giá trị khởi tạo từ điểm gương $j$, rồi loang tiếp. Hàng cnt là kết quả đã tính.

Xâu S

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int n;
string s;
int cnt[2000005];

void cal(){
    s = "." + s + "^";
    int l = 1, r = 1;
    for (int i = 1; i <= n; i ++){
        cnt[i] = max(0, min(r - i, cnt[l + (r - i)]));
        while(s[i - cnt[i]] == s[i + cnt[i]]) cnt[i] ++;
        if (i + cnt[i] > r){
            l = i - cnt[i];
            r = i + cnt[i];
        }
    }
}

int main(){
    string t;
    getline(cin, t);
    if (!t.empty() && t.back() == '\r') t.pop_back();
    for (int i = 0; i < t.size(); i ++){
        if (i) s += "#";
        s += t[i];
    }
    n = s.size();
    int res = 0;
    cal();
    for (int i = 1; i <= n; i ++){
        int a = cnt[i] - 1;
        if (i % 2 == 0) res = max(res, (a + 1) / 2 * 2);
        else res = max(res, a / 2 * 2 + 1);
    }
    cout << res << endl;
}

import sys

def main():
    t = sys.stdin.readline().rstrip('\n').rstrip('\r')
    s = '#'.join(t)
    n = len(s)
    s = '.' + s + '^'
    cnt = [0] * (n + 2)
    l, r = 1, 1
    for i in range(1, n + 1):
        c = 0
        if r - i > 0:
            c = min(r - i, cnt[l + (r - i)])
        while s[i - c] == s[i + c]:
            c += 1
        cnt[i] = c
        if i + c > r:
            l = i - c
            r = i + c
    res = 0
    for i in range(1, n + 1):
        a = cnt[i] - 1
        if i % 2 == 0:
            res = max(res, (a + 1) // 2 * 2)
        else:
            res = max(res, a // 2 * 2 + 1)
    print(res)

main()

Hai chỗ mình chỉnh lại so với code gốc

• Code gốc của mình chỉ chèn # vào giữa các kí tự (không chèn ở hai đầu) nhưng lại quy đổi ra độ dài thật bằng cnt[i] - 2 và cnt[i] - 1. Công thức này chỉ đúng khi palin dừng lại ở một kí tự ảo; nếu palin chạm mép xâu thì bị hụt 1 (ví dụ aba ra $2$, a ra $0$). Hai ví dụ của đề không chạm mép nên vẫn ra đúng, nhưng mình đã sửa lại thành đếm số kí tự thật trong đoạn như công thức ở trên.
• Ở vòng lặp đầu tiên, khởi tạo cũ l = 0, r = -1 làm chỉ số cnt[l + (r - i)] bị âm (đọc ngoài mảng, dù kết quả sau đó bị max(0, ...) che đi). Mình đổi thành l = 1, r = 1 cho an toàn.

Ngoài ra có thêm dòng bỏ kí tự '\r' cuối dòng (file tạo trên Windows) để khỏi bị tính nhầm vào xâu.

C++▶ Chạy tay từng dòng codeCách 2: chèn # rồi chạy Manacher, quy đổi bán kính ra độ dài thật.

Dữ liệu vào (stdin) – sửa thoải máiAbcbcadk %

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2using namespace std;

3

4int n;

5string s;

6int cnt[2000005];

7

8void cal(){

9 s = "." + s + "^";

10 int l = 1, r = 1;

11 for (int i = 1; i <= n; i ++){

12 cnt[i] = max(0, min(r - i, cnt[l + (r - i)]));

13 while(s[i - cnt[i]] == s[i + cnt[i]]) cnt[i] ++;

14 if (i + cnt[i] > r){

15 l = i - cnt[i];

16 r = i + cnt[i];

17 }

18 }

19}

20

21int main(){

22 string t;

23 getline(cin, t);

24 if (!t.empty() && t.back() == '\r') t.pop_back();

25 for (int i = 0; i < t.size(); i ++){

26 if (i) s += "#";

27 s += t[i];

28 }

29 n = s.size();

30 int res = 0;

31 cal();

32 for (int i = 1; i <= n; i ++){

33 int a = cnt[i] - 1;

34 if (i % 2 == 0) res = max(res, (a + 1) / 2 * 2);

35 else res = max(res, a / 2 * 2 + 1);

36 }

37 cout << res << endl;

38}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: xâu mới và mảng cnt dài $2N + 1$ ⇒ $O(N)$.
• Thời gian: mỗi lần vòng while loang thành công vượt qua mép phải $r$ thì $r$ tăng lên, mà $r$ không bao giờ giảm và không vượt quá $n + 1$, nên tổng số bước loang là $O(n)$ ⇒ cả thuật toán $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Về bản Python

Xâu mới dài tới $2 \cdot 10^6$ kí tự, Python mất khoảng 1 giây. Nếu đề giới hạn 1 giây mà chấm Python thì hơi căng, các bạn nên nộp C++ cho chắc.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 600 bộ test ngẫu nhiên (xâu dài tới 30 kí tự, có cả chữ hoa, dấu cách, #, ., ^), so với code vét cạn $O(N^3)$ – khớp hết. Với xâu $10^6$ kí tự (toàn chữ a, xen kẽ abab..., ngẫu nhiên), Manacher chạy khoảng 0.05 giây (C++) và 1 giây (Python); cách 1 với xâu toàn chữ a chạy hơn 20 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇