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] );
