QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 4224. 串

Statistics

为了让你更好地理解题面,给出若干关于字符串的定义:

  • 对于一个字符串 S=s1s2sn,定义其长度为 |S|=n
  • 对于两个字符串 S=s1s2snT=t1t2tm,称 TS 的子串,若 m=0(即 T 为空串)或者 1ijnT=sisi+1sj。若 m=0 或上述判断条件中 i 可以取到 1,则称 TS 的前缀;若 m=0 或上述判断条件中 j 可以取到 n,则称 TS 的后缀。

给定一个英文小写字母构成的字符串 S,你需要找到一个尽可能长的字符串序列 (T0,T1,,Tl),满足:

  • T0S 的子串;
  • 1il|Ti||Ti1|=1
  • 1il,存在 S 的一个长度为 |Ti|+1 的子串 Si,使得 Si 的长度为 |Ti1| 的前缀为 Ti1,长度为 |Ti| 的后缀为 Ti

输出这样的字符串序列的长度的最大值(即 l 的最大值)。

输入格式

本题有多组测试数据

输入的第一行为一个整数 T,表示测试数据组数。对于每组测试数据,输入一行一个英文小写字母构成的字符串 S

输出格式

对于每组测试,数据输出一行一个整数,表示题目描述中字符串序列长度的最大值。

样例数据

样例 1 输入

3
abcd
abab
a

样例 1 输出

2
3
0

样例 1 解释

下文中使用符号 ϵ 表示空串。

对于第一组测试数据,可以找到如下字符串序列:T0=ϵ,T1=b,T2=cd,其中 S1=ab,S2=bcd

对于第二组测试数据,可以找到如下字符串序列:T0=ϵ,T1=b,T2=ab,T3=bab,其中 S1=ab,S2=bab,S3=abab

对于第三组测试数据,可以找到如下字符串序列:T0=ϵ

样例 2

见下发文件。

该组样例中的字符串长度有一定梯度,你可以利用该组样例对程序进行检查。

样例 3

见下发文件。

该组样例满足特殊性质 A。

子任务

|S| 表示测试点中所有测试数据的字符串长度和。

对于 100% 的测试数据,T11|S|5×1051|S|1.5×106

测试点编号 |S| |S| 特殊性质
12 30 150
35 200 800
68 1000 3000
911 5×105 1.5×106 A
1215 6×104 3×105
1620 5×105 1.5×106

特殊性质 A:字符串中的每个字符在小写字母中独立均匀随机生成。

提示

本题输入输出量较大,请使用较为快速的输入输出方式。

例如,若你的代码使用了 cincout 作为输入输出方式,你可以选择在代码的输入输出重定向语句freopen 语句、 fopen 语句等)之后加入以下语句加速输入输出速度。

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

加入该语句后不建议同时使用 cin, cout 和其他输入输出方式。