Một vài bài tập về Palindrome

Người viết: Nguyễn Hoành Tiến   21/04/2008
Một vài bài tập về Palindrome
Nguyến Hoành Tiến
Palindrome hay còn gọi là xâu đối xứng, xâu đối gương là tên gọi của những xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. VD: MADAM, IOI,... Nhờ tính chất đặc biệt đó mà có khá nhiều bài tập có liên quan đến Palindrome, phần lớn trong chúng thường đi kèm với QHĐ. Tôi xin giới thiệu với các bạn một vài bài tập như vậy.
Bài 1: Xem một xâu có phải là Palindrome hay không?
Đây là một bài cơ bản, nhưng quan trọng vì nó được đề cập đến trong nhiều bài tập khác. Cách làm tốt nhất là duyệt đơn thuần mất O(N).
function is_palindrome(s: string): boolean; var i, n : integer; begin n := length(s); for i := 1 to (n div 2) do if s[i] <> s[n+1-i] then begin is_palindrome := false; exit; end; is_palindrome := true; end;
Một đoạn chương trình khác :
function is_palindrome(s : string) : boolean; var i, j : integer; begin i := 1; j := length(n); while i begin if s[i] <> s[j] then begin is_palindrome := false; exit; end; inc(i); dec(j); end; is_palindrome := true; end;
Bài 2: Cho một xâu S <= 1000 kí tự; tìm palindrome dài nhất là xâu con của S ( Xâu con là một dãy các kí tự liên tiếp ).
Đây cũng là một bài cơ bản với nhiều cách làm.
Cách 1: QHĐ
Dùng mảng F[i, j] có ý nghĩa: F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j của S có/không là palindrome.
Ta có công thức là:
* F[i, i] = True * F[i, j] = F[i+1, j-1]; ( nếu s[i] = s[j] ) * F[i, j] = False; ( nếu s[i] <> s[j] )
Đoạn chương trình như sau:
FillChar( F, sizeof(F), false ); for i := 1 to n do F[i, i] := True; for k := 1 to (n-1) do for i := 1 to (n-k) do begin j := i + k; F[i, j] := ( F[i+1, j-1] ) and (s[i] = s[j] ); end;
Kết quả là : i(Max(j-i+1) <=j thỏa F[i,j] = True.
Độ phức tạp thuật toán là 0(N2).
Chú ý : Với N lớn, ta phải thay mảng 2 chiều F bằng 3 mảng 1 chiều và dùng thêm biến max lưu giá trị tối ưu.
Cách 2: Duyệt có cận.
Ta xét từng vị trí i:
+ xem a[i] có phải là tâm của Palindrome có lẻ kí tự không?
( ví dụ Palindrome MADAM có tâm là kí tự D )
+ xem a[i] và a[i+1] có phải là tâm của Palindrome có chẵn kí tự không?
( ví dụ Palindrome ABBA có tâm là 2 kí tự BB )
với mỗi kí tự ta tìm palindrome dài nhất nhận nó là tâm, cập nhập lại kết quả khi duyệt. Ta duyệt từ giữa ra để dùng kết quả hiện tại làm cận.
Đoạn chương trình như sau:
procedure Lam; var i, j : Longint ; { } procedure try( first, last : Longint ); var đ : Longint; begin if first = last then begin đ := 1; dec(first); inc(last); end else đ := 0; repeat if (first < 1) or (last > N) then break; if s[i] = s[j] then begin đ := đ + 2; first := first - 1; last := last + 1; end else break; until false; if max < dd then max := dd; end; { } begin i := n div 2; j := n div 2 + 1; max := 1; while (i > max div 2) and (j <= N-max div 2) do begin if i > max div 2 then begin try( i