配点 : 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