Người viết: Nguyễn Hoành Tiến 21/04/2008 Một vài tập Palindrome Nguyến Hồnh Tiến Palindrome hay cịn gọi xâu đối xứng, xâu đối gương tên gọi xâu kí tự mà viết từ phải qua trái hay từ trái qua phải xâu khơng thay đổi VD: MADAM, IOI, Nhờ tính chất đặc biệt mà có nhiều tập có liên quan đến Palindrome, phần lớn chúng thường kèm với QHĐ Tôi xin giới thiệu với bạn vài tập Bài 1: Xem xâu có phải Palindrome hay khơng? Đây bản, quan trọng đề cập đến nhiều tập khác Cách làm tốt duyệt đơn O(N) function is_palindrome(s: string): boolean; var i, n : integer; begin n := length(s); for i := to (n div 2) 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 xâu S max div 2) and (j max div then begin try( i, i ); try( i, i+1 ); end; if j = n) end; Vậy thuật toán có độ phức tạp tính tốn O(N2), chi phí nhớ O(N) Bài : Pal - Ioicamp - Marathon 2005-2006- tuần 17 Cho xâu, hỏi có xâu palindrome; xâu gồm kí tự khơng cần liên tiếp ( độ dài