Problem1090--最少回文串分割

1090: 最少回文串分割

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 13
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI听说同学们最近学习了回文串算法,现在它想考考你~
PIPI给你一个只含小写字母的字符串,请你将这个字符串拆分成几段,要求每段都是回文串,同时要求段数尽可能少。
racecar本身为回文串,故答案为1
fastcar只能拆成'f','a','s','t','c','a','t',答案为7
aaabcac可以拆成'aaa','b','cac',答案为3

Input

多组输入
第一行为一个字符串,长度不超过1000

Output

输出拆分的最小段数

Sample Input

racecar
fastcar
aaadbccb

Sample Output

1
7
3

Source/Category