← 返回题目列表

AtCoder · ttpc2023_h

H. 404 查托找到

中文机器翻译题面 查看原题

配点 : 100 点

返回顶部

将得到

問題文

N 字符串 S_1, S_2, \dots, S_N 。非空字符串 包含 T 的数量。

  • 文字列 S_1, S_2, \dots, S_N , 选择最大化T 作为(连续)子字符串的正好有 考虑 1 。

制約

  • 1 \le N \le 10^5
  • 1 \le |S_i| \le 10^6\ (1 \le i \le N)
  • \left(\sum_{i=1}^{N} |S_i|\right) \le 10^6
  • S_i\ (1 \le i \le N) 是一串小写字母

入力

输入是按以下格式从标准输入给出的。

N
S_1
S_2
\vdots
S_N

出力

打印答案。 来自


入力例 1

2
abc
ca

出力例 1

5

T = {}a 的情况, 因为包含S_1 = {}abc 和 按字典顺序比较 S_2 = {}ca 可以得到第 2 件 a 作为子字符串,所以不满足条件。 因为包含

T = {}ab 的情况, 因为包含S_1 = {}abc 仅有的 ab 作为子字符串,所以满足条件。

T = {}d 的情况, 因为包含S_1 = {}abc 也是 使得 S_2 = {}ca 也是 使得 d 作为子字符串,因此不满足条件。 没有满足

满足条件的字符串为 有\(5\)个 T = {}b, ab, bc, ca, abc 可以得到第 5 件。


入力例 2

2
aab
aab

出力例 2

0

T = {}ab 的情况, 因为包含S_1 = {}aab 和 按字典顺序比较 S_2 = {}aab 可以得到第 2 件 ab 作为子字符串,所以不满足条件。 因为包含

条件的字符串。


入力例 3

1
aba

出力例 3

5

满足条件的字符串为 有\(5\)个 T = {}a, b, ab, ba, aba 可以得到第 5 件。


入力例 4

3
tokyoinstituteoftechnology
tokyomedicalanddentaluniversity
instituteofsciencetokyo

出力例 4

905