Problem2821--切割字符串

2821: 切割字符串

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个回文串。例如，“abcaacba”是一个回文串，“abcaaba”则不是一个回文串。
小科看到什么字符串都想要把它变成回文的。他可以通过切割字符串，使得切割完之后得到的子串都是回文的。
现在小科想知道他最少切割多少次就可以达到目的。例如，对于字符串“abaacca”，最少切割一次，就可以得到“aba”和“acca”这两个回文子串。

Input

输入的第一行是一个整数 T (T <= 20) ，表示一共有 T 组数据。
接下来的 T 行，每一行都包含了一个长度不超过的 1000 的字符串，且字符串只包含了小写字母。

Output

对于每组数据，输出一行。该行包含一个整数，表示最少切割的次数，使得切割完得到的子串都是回文的。

Sample Input Copy 

<dl><dd>3
abaacca
abcd
abcba
</dd></dl>

Sample Output Copy 

<dl><dd>1
3
0
</dd></dl>

HINT

【样例说明】
对于第一组样例，最少切割 1 次，将原串切割为“aba”和“acca”两个回文子串。
对于第二组样例，最少切割 3 次，将原串切割为“a”、“b”、“c”、“d”这四个回文子串。
对于第三组样例，不需要切割，原串本身就是一个回文串。

Source/Category

动态规划 NOI level5 
[Submit] [Status]