Đếm số Palindrome

Xem dạng PDF

Gửi bài giải


Điểm: 0,15 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Cổ điển
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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'

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.

Input

Gồm một dòng chứa xâu ký tự ~s~ gồm không quá ~255~ ký tự.

Output

Gồm một dòng duy nhất ghi ~k~ là số lượng ít nhất các palindrome trong biểu diễn tìm được.

Sample Input

bobseesanna

Sample Output

3

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.