Longest Common Prefix

题目描述

给定一个长度为 $n$ 的字符串 $s$。

对于每一个位置 $i$（满足 $1 \le i \le n$），定义字符串 $t_i$ 为：

• 从字符串 $s$ 中删除第 $i$ 个字符后得到的新字符串；
• 其余字符的相对顺序保持不变。

对于两个字符串 $x$ 和 $y$，定义：

表示它们的最长公共前缀（Longest Common Prefix）的长度，即最大的整数 $\ell \ge 0$，满足：

你的任务是：

选择两个不同的位置 $i$ 和 $j$，使得：

尽可能大，并输出这个最大值。

形式化地，你需要计算：

你只需要输出这个最大值，不需要输出对应的 $i,j$。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 2 \times 10^5$），表示测试用例数量。

接下来每组测试数据包含一行，一个字符串 $s$。

保证：

• $2 \le |s| \le 5 \times 10^5$
• 字符串仅由小写英文字母组成
• 所有测试用例的字符串长度之和不超过 $5 \times 10^5$

输出格式

对于每组测试数据，输出一个整数，表示：

的值。

每个答案占一行。

样例输入

5
abac
abbbb
cbacb
babcc
aa

样例输出

2
4
3
4
1