(5 ĐIỂM)PALINDROME LÀ XÂU KÝ TỰ MÀ NẾU ĐỌC NÓ TỪ TRÁI SANG PHẢI CŨNG...

BÀI 4 : (5 điểm)Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái tađược cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy cácpalindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là palindrome. Ví dụ: Xâu ‘bobseesanna’ có thể biểu diễn dưới dạng dãy các palindrome theo nhiềucách, chẳng hạn‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’Yêu cầu: Cho xâu ký tự s, cần tìm cách biểu diễn xâu s dưới dạng một dãy gồm mộtsố ít nhất các palindrome. Ví dụ: Cho s = ‘bobseesanna’, do ta có ‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’ vàkhông thể biểu diễn ‘bobseesanna’ bởi ít hơn là 3 palindrome nên biểu diễn này chính làbiểu diễn cần tìm.Dữ liệu: Vào từ file văn bản PALINDR.INP gồm một dòng chứa xâu ký tự s gồmkhông quá 255 ký tự.Kết quả: Đưa ra màn hình đồng thời ghi vào file văn bản PALINDR.OUT:- Dòng đầu tiên ghi k là số lượng ít nhất các palindrome trong biểu diễn tìm được;- Dòng thứ i trong số k dòng tiếp theo ghi palindrome p

i

(i = 1, 2, ..., k) sao cho :s = p

1

p

2

...p

k

.Ví dụPALINDR.INP PALINDR.OUT PALINDR.INP PALINDR.OUTbobseesanna 3aabbaaaabb 2bobaabbaaaabbseesanna



HẾT



Ghi chú :- Các tập tin bài làm phải đặt theo qui định BL1.PAS, BL2.PAS, BL3.PAS,BL4.PAS;- Đề thi có 03 trang;- Giám thị không giải thích gì thêm.