#2127. 奶龙的 3G 信号实验

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

CQUPT(重庆邮电大学) 的某个神秘实验室里,
奶龙正在测试一套 3G 超远古信号发送系统

由于 3G 网络极其不稳定,每次发送字符串信号时,
都会随机丢失一个字符

奶龙觉得这太不抽象了,于是他决定:
我自己来决定删哪一位!

nailiong3g


题目描述

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

对于每一个位置 i (1 ≤ i ≤ n),定义 为:

从字符串 s删除第 i 个字符 后得到的字符串
(其余字符的相对顺序保持不变)


最长公共前缀(LCP)

对于两个字符串 xy
定义 lcp(x, y) 为它们的 最长公共前缀长度,即:

最大的整数 ℓ ≥ 0,使得
x[1..ℓ] = y[1..ℓ]


奶龙的问题

奶龙会选择 两个不同的位置 i ≠ j 进行删除操作,
得到字符串

请你帮奶龙计算:

所有 i ≠ j
的最大值

形式化地,你需要求:

⚠️ 注意:
不需要输出位置 ij,只需输出最大值。

输入格式

第一行一个整数 T,表示测试用例数量

接下来 T 行,每行一个字符串 s,满足: 仅包含小写英文字母
所有测试用例中 |s| 的总和不超过

输出格式

对于每个测试用例,输出一行一个整数,
表示最大可能的

样例

样例 1

输入

5
abac
abbbb
cbacb
babcc
aa

输出

2
4
3
4
1

解释(非唯一方案)

  • 对于字符串 abac: 删除第 3 位字符 'a' 与删除第 4 位字符 'c',得到的字符串分别为 abcaba,其最长公共前缀长度为 2,这是可以达到的最大值。

  • 对于字符串 abbbb: 删除任意一个 'b',得到的字符串均为 abbb, 因此最长公共前缀长度为 4

  • 对于字符串 cbacb: 可以选取合适的两个删除位置,使得得到的字符串在前 3 个字符完全一致。

  • 对于字符串 babcc: 删除相邻相同字符 'c' 中的任意一个, 可以得到两个完全相同的字符串,最长公共前缀长度为 4

  • 对于字符串 aa: 删除任意一个字符后均得到 "a", 最长公共前缀长度为 1


样例 2

输入

1
abcde

输出

3

数据范围与提示

字符串 s 仅由小写英文字母组成, 所有测试用例中字符串长度之和不超过