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