#P12762. 串串

    ID: 11948 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400字符串后缀数组单调栈数据结构2025“钉耙编程”中国大学生算法设计暑期联赛(1)

串串

串串

Problem Description

给你 nn(1≤n≤501 \leq n \leq 50)个仅有小写字母组成的字符串 s1,s2,⋯ ,sns_1, s_2, \cdots, s_n,每个字符串的长度不一定相等。你需要选择一个字符串 tt ( tt 不一定在 ss 中选)。神圣值 aa 的定义如下:

  • 对于每个字符串 sis_i,你有两种选择:
  • 忽略这个字符串。此时该串的神圣值 ai=0a_i = 0。
  • 从 sis_i 中选择一个与 tt 相等的子串。假设你选的这个子串为 [L,R][L, R],那么 ai=La_i = L。 你需要在选择至少两个串的前提下,最大化 $$|t| \times \sum_{i = 1}^{n} a_i$$

Input

第一行输入一个整数 TT(1≤T≤501 \le T \le 50),表示测试的总数。 对于每个测试样例, 第一行输入一个数 nn(1≤n≤501 \leq n \leq 50) ,表示字符串的个数。 接下来 nn 行,每行一个字符串 sis_i (1≤∣s∣≤1051 \leq |s| \leq 10^5)。保证样例中 ∑∣s∣≤1.1×106\sum |s| \leq 1.1 \times10^6 。

Output

对于每个样例,输出一个数,∣t∣×∑i=1nai|t| \times \sum_{i = 1}^{n} a_i 的最大值。若无法取到两个串,请输出 00。

Sample Input

2
3
a
aa
aaa
1
abc

Sample Output

6
0

Hint

对于第一个样例,我们选择 t=aat = aa。这样神圣值可以选择为 aa = [0, 1, 2]。因此答案为 6。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(1)