为了让你更好地理解题面,给出若干关于字符串的定义:
- 对于一个字符串 S=s1s2⋯sn,定义其长度为 |S|=n。
- 对于两个字符串 S=s1s2⋯sn 和 T=t1t2⋯tm,称 T 为 S 的子串,若 m=0(即 T 为空串)或者 ∃1≤i≤j≤n,T=sisi+1⋯sj。若 m=0 或上述判断条件中 i 可以取到 1,则称 T 为 S 的前缀;若 m=0 或上述判断条件中 j 可以取到 n,则称 T 为 S 的后缀。
给定一个英文小写字母构成的字符串 S,你需要找到一个尽可能长的字符串序列 (T0,T1,…,Tl),满足:
- T0 是 S 的子串;
- ∀1≤i≤l,|Ti|−|Ti−1|=1;
- ∀1≤i≤l,存在 S 的一个长度为 |Ti|+1 的子串 S′i,使得 S′i 的长度为 |Ti−1| 的前缀为 Ti−1,长度为 |Ti| 的后缀为 Ti。
输出这样的字符串序列的长度的最大值(即 l 的最大值)。
输入格式
本题有多组测试数据。
输入的第一行为一个整数 T,表示测试数据组数。对于每组测试数据,输入一行一个英文小写字母构成的字符串 S。
输出格式
对于每组测试,数据输出一行一个整数,表示题目描述中字符串序列长度的最大值。
样例数据
样例 1 输入
3
abcd
abab
a
样例 1 输出
2
3
0
样例 1 解释
下文中使用符号 ϵ 表示空串。
对于第一组测试数据,可以找到如下字符串序列:T0=ϵ,T1=b,T2=cd,其中 S′1=ab,S′2=bcd。
对于第二组测试数据,可以找到如下字符串序列:T0=ϵ,T1=b,T2=ab,T3=bab,其中 S′1=ab,S′2=bab,S′3=abab。
对于第三组测试数据,可以找到如下字符串序列:T0=ϵ。
样例 2
见下发文件。
该组样例中的字符串长度有一定梯度,你可以利用该组样例对程序进行检查。
样例 3
见下发文件。
该组样例满足特殊性质 A。
子任务
设 ∑|S| 表示测试点中所有测试数据的字符串长度和。
对于 100% 的测试数据,T≥1,1≤|S|≤5×105,1≤∑|S|≤1.5×106。
测试点编号 | |S|≤ | ∑|S|≤ | 特殊性质 |
---|---|---|---|
1∼2 | 30 | 150 | 无 |
3∼5 | 200 | 800 | 无 |
6∼8 | 1000 | 3000 | 无 |
9∼11 | 5×105 | 1.5×106 | A |
12∼15 | 6×104 | 3×105 | 无 |
16∼20 | 5×105 | 1.5×106 | 无 |
特殊性质 A:字符串中的每个字符在小写字母中独立均匀随机生成。
提示
本题输入输出量较大,请使用较为快速的输入输出方式。
例如,若你的代码使用了 cin
和 cout
作为输入输出方式,你可以选择在代码的输入输出重定向语句(freopen
语句、 fopen
语句等)之后加入以下语句加速输入输出速度。
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
加入该语句后不建议同时使用 cin, cout
和其他输入输出方式。