#PQJ941x4224. QOJ 941_4224

    ID: 3075 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:LNOI 2022字符串前缀和枚举

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 和其他输入输出方式。