Palindrom

Palindrom (IOI 2000)

Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.

Hướng dẫn:

Bài toán này có một công thức QHĐ như sau:
Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng.
Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có công thức sau để tính L(i,j):
• L(i,i)=0.
• L(i,j)=L(i+1,j–1) nếu S[i]=S[j]
• L(i,j)=max(L(i+1,j), L(i,j–1)) nếu S[i]≠S[j] Bạn đọc dễ dàng có thể kiểm chứng công thức đó. Ta có thể cài đặt trực tiếp công thức đó bằng phương pháp đệ quy có nhớ. Tuy nhiên khi đó chi phí không gian là O(n2). Có một phương pháp cài đặt tiết kiệm hơn tuy nhiên phương pháp đó khá phức tạp. Ta có thuật toán đơn giản hơn như sau: Gọi P là xâu đảo của S và T là xâu con chung dài nhất của S và P. Khi đó các kí tự của S không thuộc T cũng là các kí tự cần thêm vào để S trở thành đối xứng. Đáp số của bài toán sẽ là n–k, với k là độ dài của T.

Ví dụ: S=edbabcd, xâu đảo của S là P=dcbabde. Xâu con chung dài nhất của S và P là T=dbabd. Như vậy cần thêm 2 kí tự là e và c vào để S trở thành xâu đối xứng.