Palindrome
Thứ Năm, 25 tháng 6, 2015
: Palindrome (10 điểm) Tên chương trình: PALINDR.PAS
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ác palindrome nếu
như ta coi xâu chỉ gồm một ký tự luôn là một palindrome.
Ví dụ: Xâu ‘bobseesanna’ có thể biểu
diễn dưới dạng dãy các palindrome theo nhiều cá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 số í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: Vào từ tập tin văn bản PALINDR.IN, gồm một dòng chứa xâu ký tự
s gồm không quá 255 ký tự.
Kết quả: Đưa ra tập tin văn bản PALINDR.OU:
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 pi (i=1, 2, ..., k) sao cho s = p1p2...pk.
PALINDR.IN
|
PALINDR.OU
|
|
PALINDR.IN
|
PALINDR.OU
|
bobseesanna
|
3
bob
sees
anna
|
|
aabbaaaabb
|
2
aa
bbaaaabb
|
All comments [ 0 ]
Your comments