Tham khảo tại CP-Algo.

Nhận xét

Nhận thấy nếu xâu độ dài $L$ đối xứng có tâm tại $i$, thì xâu độ dài $L-2,L-4$ … tâm $i$ cũng sẽ đối xứng.

Định nghĩa

Các kí tự được đánh số từ $1$.

Gọi $d1_i$ = độ dài xâu đối xứng tâm lẻ đặt tại $i$ (không tính $i$), $d2_i$ = xâu đối xứng tâm chẵn tại $i$, nghĩa là xâu có tâm là 2 kí tự $s_i$ và $s_{i+1}$

Gọi $p_i$ = độ dài xâu dài nhất về $2$ phía nhận $i$ làm tâm

Gọi $l, r$ là vị trí của xâu palindrome gần với vị trí $i$ nhất (bên phải nhất) tính đến thời điểm hiện tại.

Ban đầu $l = 0, r = -1$

Giải thuật

Tính mảng d1

Xét các trường hợp:

• Nếu $i>r$, chạy thuật toán trâu

  while(chưa tràn khỏi xâu và $s[i - d1_i] == s[i + d1_i]$) $d1_i++$;

• Ngược lại, xét trường hợp $i \leq r$, nghĩa là $i$ thuộc vào đoạn palin gần nhất đang xét. Nhận thấy ở đoạn $[l,r]$, vị trí đối xứng với vị trí $i$ qua tâm $\frac{l+r}{2}$ là vị trí $l+(r-i)$

  Đặt $j=l+(r-i)$. Ở đây ta tiếp tục có $2$ TH con

  • Đoạn $[j-d1_j+1,j+d1_j-1]$ nằm trong đoạn $[l,r]$. Vì $s_j$ đối xứng với $s_i$ mà đoạn to $[l,r]$ đối xứng qua tâm $\Rightarrow$ đoạn $[j-d1_j+1,j+d1_j-1]$ và $[i-d1_j+1,i+d1_j-1]$ đối xứng. Như vậy ta gán $d1_i = d1_j$.Tham khảo hình minh hoạ

  

  • Đoạn $[j-d1_j+1,j+d1_j-1]$ chỉ giao 1 phần với đoạn $[l,r]$. Lúc này ta không thể kết luận được $d1_i = d1_j$, bởi vì mình không quản lý cái phần nằm ngoài đoạn $[l,r]$, nên chưa đủ cơ sở để khẳng định $d1_i = d1_j$. Khi đó ta gán $d1_i=r-i$, và tiếp tục chạy thuật trâu để mở rộng tâm ra. Hình minh hoạ:

  

• Lưu ý, sau khi xét tất cả TH trên xong, nhớ update lại $l, r$

  if $(i + d1_i > r)$ $l = i - d1_i$, $r = i + d1_i;$

Tính mảng d2

Thêm các kí tự DUMMY vào đầu, cuối, và giữa các kí tự xâu, nghĩa là các kí tự mà không bao giờ xuất hiện trong xâu.

Ví dụ xâu “orz” -> “.o.r.z.” với DUMMY = ‘.’

Chạy thuật toán Manacher với tâm lẻ trên xâu mới, tạm gọi mảng này là mảng $d[]$

Lúc này nhận thấy các xâu đối xứng tâm chẵn trên xâu gốc đã trở thành xâu đối xứng tâm lẻ với tâm đặt tại các kí tự DUMMY trên xâu mới.

Như vậy ta có $d2_i=\dfrac{d_{2 \times i + 1}}{2}$ (vì thêm các kí tự DUMMY làm số kí tự gấp đôi lên)

Độ phức tạp

Nhận xét mỗi lần lặp $r$ sẽ được tăng lên ít nhất $1$ đơn vị, nên độ phức tạp của thuật toán sẽ là $O(n)$.

Các bạn có thể tham khảo chi tiết chứng minh tại link ở đầu bài.

Cài đặt mẫu

• manacher.cpp
• kc97ble

Bài tập áp dụng

• CSES 1111