UOJ Logo

NOI.AC

1S 256MB

#34. palindrome

Statistics

回文串

题目描述

小 $D$ 最近在学习回文串的有关知识。对于字符串 $S=S_1S_2S_3\cdots S_{n-1}S_n$,记 $S$ 的反串 $S^R=S_nS_{n-1}S_{n-2}\cdots S_2S_1$。我们称字符串 $S$ 是回文串,当且仅当 $S=S^R$。

小 $D$ 发现回文串很少,他决定定义一些新的东西。定义字符串 $S=S_1S_2S_3\cdots S_{n-1}S_n$ 和 $T=T_1T_2T_3\cdots T_{m-1}T_m$ 的 为 $S_1S_2S_3\cdots S_{n-1}S_nT_1T_2T_3\cdots T_{m-1}T_m$,记作 $S\circ T$。

小 $D$ 发现,字符串之和满足结合律但不满足交换律,即 $(A\circ B)\circ C=A\circ (B\circ C)$ 成立,但 $A\circ B=B\circ A$ 不一定成立。

小 $D$ 定义字符串 $S$ 的一个拆分,为满足 $A_1\circ A_2\circ A_3\circ \cdots \circ A_L$ 的字符串序列 $A=[A_1,A_2,\cdots,A_L]$。定义这样的一个拆分的长度为 $L$。

小 $D$ 定义一个拆分的反拆分为序列 $A^R=[A_L,A_{L-1},\cdots,A_2,A_1]$。定义一个拆分是回文的,当且仅当 $A=A^R$(两个序列相等定义为同样位置的元素对应相等)。

小 $D$ 现在给出了字符串 $S$,想要求出 $S$ 的最长(即长度最大)的回文拆分序列有多长。请你帮帮他。

输入格式

本题包含多组数据,输入的第一行为一个整数 $T$,表示测试数据组数。

接下来 $T$ 行,每行一个字符串,表示这组数据中的 $S$。保证 $S$ 仅有小写字母组成。

输出格式

对于每组测试数据,输出一行一个整数表示答案。

样例输入 1

4
bonobo
deleted
racecar
racecars

样例输出 1

3
5
7
1

样例解释 1

以下为每组测试数据中的最优方案:

  • bo / no / bo
  • d / e / let / e / d
  • r / a / c / e / c / a / r
  • racecars

样例输入输出 2

见下发文件 ex_palindrome2.in/out

数据规模与约定

本题共 $10$ 个测试数据,每个测试数据 $10$ 分。以下为部分分分布($\lvert S\rvert$ 表示字符串 $S$ 的长度):

对于前 $10\%$ 的数据,$1\le \lvert S\rvert \le 5$;
对于另 $20\%$ 的数据,$1\le \lvert S\rvert \le 30$;
对于另 $20\%$ 的数据,$1\le \lvert S\rvert \le 200$;
对于另 $20\%$ 的数据,$1\le \lvert S\rvert \le 2000$;
对于另 $20\%$ 的数据,$1\le \lvert S\rvert \le 10^5$;
对于 $100\%$ 的数据,$1\le T\le 20$,$1\le \lvert S\rvert \le 10^6$,保证 $S$ 仅有小写字母组成。

时间限制:$2\mathtt{s}$

空间限制:$512\mathtt{MB}$

样例数据

样例数据