QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4224. 串

Statistics

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

  • 对于一个字符串 $S = s_1 s_2 \cdots s_n$,定义其长度为 $\lvert S \rvert = n$。
  • 对于两个字符串 $S = s_1 s_2 \cdots s_n$ 和 $T = t_1 t_2 \cdots t_m$,称 $T$ 为 $S$ 的子串,若 $m = 0$(即 $T$ 为空串)或者 $\exists 1 \le i \le j \le n$,$T = s_i s_{i + 1} \cdots s_j$。若 $m = 0$ 或上述判断条件中 $i$ 可以取到 $1$,则称 $T$ 为 $S$ 的前缀;若 $m = 0$ 或上述判断条件中 $j$ 可以取到 $n$,则称 $T$ 为 $S$ 的后缀。

给定一个英文小写字母构成的字符串 $S$,你需要找到一个尽可能长的字符串序列 $(T_0, T_1, \ldots, T_l)$,满足:

  • $T_0$ 是 $S$ 的子串;
  • $\forall 1 \le i \le l$,$\lvert T_i \rvert - \lvert T_{i - 1} \rvert = 1$;
  • $\forall 1 \le i \le l$,存在 $S$ 的一个长度为 $\lvert T_i \rvert + 1$ 的子串 $S'_i$,使得 $S'_i$ 的长度为 $\lvert T_{i - 1} \rvert$ 的前缀为 $T_{i - 1}$,长度为 $\lvert T_i \rvert$ 的后缀为 $T_i$。

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

输入格式

本题有多组测试数据

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

输出格式

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

样例数据

样例 1 输入

3
abcd
abab
a

样例 1 输出

2
3
0

样例 1 解释

下文中使用符号 $\epsilon$ 表示空串。

对于第一组测试数据,可以找到如下字符串序列:$T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{cd}$,其中 $S'_1 = \texttt{ab}, S'_2 = \texttt{bcd}$。

对于第二组测试数据,可以找到如下字符串序列:$T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{ab}, T_3 = \texttt{bab}$,其中 $S'_1 = \texttt{ab}, S'_2 = \texttt{bab}, S'_3 = \texttt{abab}$。

对于第三组测试数据,可以找到如下字符串序列:$T_0 = \epsilon$。

样例 2

见下发文件。

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

样例 3

见下发文件。

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

子任务

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

对于 $100 \%$ 的测试数据,$T \ge 1$,$1 \le \lvert S \rvert \le 5 \times {10}^5$,$1 \le \sum \lvert S \rvert \le 1.5 \times {10}^6$。

测试点编号 $\lvert S \rvert \le$ $\sum \lvert S \rvert \le$ 特殊性质
$1 \sim 2$ $30$ $150$
$3 \sim 5$ $200$ $800$
$6 \sim 8$ $1000$ $3000$
$9 \sim 11$ $5 \times {10}^5$ $1.5 \times {10}^6$ A
$12 \sim 15$ $6 \times {10}^4$ $3 \times {10}^5$
$16 \sim 20$ $5 \times {10}^5$ $1.5 \times {10}^6$

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

提示

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

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

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

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