W3: Xâu đối xứng

Bài toán

Đối xứng là một vẻ đẹp của vũ trụ. Ta hãy cùng nhau xem xét bài toán sau. (Đây là một bài toán khá nổi tiếng trong tin học). Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
Vi dụ aba, hellolleh là những xâu đối xứng.

Đầu vào

S
Với S là xâu ký tự bất kỳ

Đầu ra

N S’
Với N là số ký tự cần thêm vào để biến xâu S thành xâu đối xứng S’