2011年8月29日 星期一

11584 - Partitioning by Palindrome



我們稱一個字串是「迴文字」表示該字串從頭寫到尾與從尾寫到頭是一模一樣的,例如"racecar"就是一個迴文字,但"fastcar"並不是。

我們可以把一個字串切割成數個群組,每個群組長度最少一個字元,例如("race", "car")就是將"racecar"切割成兩段的情況。

給定一個字串,我們一定可以將該字串作切割,並使切割後的每一段各自成為一個迴文字(一個字元本身就是一個迴文字)。本題想請問你:給定一個字串,將該字串切割成數個群組,並使每個群組皆為迴文字,其最少的群組數為多少?例如:
  • "racecar"本身就是一個迴文字,所以群組數最少為1。
  • "fastcar"的最少迴文群組為7 ('f', 'a', 's', 't', 'c', 'a', 'r')。
  • "aaadbccb"最少有個三迴文群組("aaa", "d", "bccb")。

輸入一開始給定一個整數 n 表示測試資料的組數,每組資料有一列字串,長度介於1~1000個小寫字元,字串內不會有空白字元。

請每組測試資料輸出一個整數,表示字串的最少迴文群組個數。


Sample Input

3
racecar
fastcar
aaadbccb

Sample Output

1
7
3

原文出處

沒有留言:

張貼留言