#2484. 「CEOI2017」Palindromic Partitions

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

给出一个只包含小写字母字符串,要求你将它划分成尽可能多的小块,使得这些小块构成回文串。
例如:对于字符串 abcab,将他分成 ab c ab 或者 abcab 就是构成回文串的划分方法,abc ab 则不是。

输入格式

第一行输入一个整数 T 表示数据组数。
接下来的 T 行,每行输入一个字符串,代表你需要处理的字符串,保证该字符串只包含小写字母。

输出格式

输出 T 行,对于每个输入的字符串,输出一行包含一个整数 x ,表示该字符串最多能分解成 x 个小块,使得这些小块构成回文串。

样例

样例输入

4
bonobo
deleted
racecar
racecars

样例输出

3
5
7
1

数据范围与提示

对于 100\% 的数据,有 1\le T\le 10 。设 L 为单个字符串的长度,则 1\le L\le 10^6

  • 子任务 1( 15\% ): 1\le L\le 30
  • 子任务 2( 20\% ): 1\le L\le 300
  • 子任务 3( 25\% ): 1\le L\le 10^4
  • 子任务 4( 40\% ): 无特殊限制。