PALI2 - Tách chuỗi đối xứng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

      Chuỗi đối xứng (palindrome) là chuỗi mà nếu ta đọc từ trái sang phải hay từ phải sang trái thì đều giống nhau. Ví dụ chuỗi 'abcba' là chuỗi đối xứng. Một ký tự duy nhất cũng được gọi là chuỗi đối xứng.

      Một chuỗi S bất kỳ luôn có thể ghép được từ các chuỗi đối xứng. Ví dụ chuỗi 'bobseesanna' có một số cách ghép như sau:

1) 'b' + 'o' + 'b' + 'sees' + 'a' + 'n' + 'n' + 'a'

2) 'bob' + 'sees' + 'anna'

3) 'bob' + 's' + 'ee' + 's' + 'anna'

     Tổng quát S = P1 + P2 +...+ Pk. với P1, P2,... , Pk là các chuỗi đối xứng. Bạn hãy tìm cách biểu diễn S sao cho k là bé nhất. Trong ví dụ trên, k = 3 (cách ghép số 2).

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 2.000) biểu thị chiều dài chuỗi S.

- Dòng thứ hai là chuỗi S gồm n ký tự là các chữ cái la tinh thường từ a đến z.

Dữ liệu xuất:

- Dòng thứ nhất là số nguyên k.

- Trong k dòng tiếp theo, tại dòng thứ i là chuỗi đối xứng Pi. Nếu có nhiều cách biểu diễn, chỉ cần in ra một cách bất kỳ.

Ví dụ

  • input
    11
    bobseesanna
    output
    3
    bob
    sees
    anna
  • input
    4
    noon
    output
    1
    noon
Back to Top