← 返回题目列表

AtCoder · kupc2014_k

K. 弱点

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

你是 KUPC 的成员,不幸的是你在编码时被一群怪物打断了。 你,一个才华横溢的程序员,必须用适当的字符串攻击怪物才能打败它们。

该怪物是 N 有一具尸体。每个怪物都有自己的弱点。i 番目 ( i=1,….,N ) 怪物的弱点是字符串 由S_i代表。 第 i 个怪物是一个字符串 当受到 T 攻击时, 如果它是T 是 它可能以 S_i 的子串,则该怪物是 受到 |T| 的伤害。 如果不是子串,则损坏为 0 。

您可以使用字符串 决定一个 T ,N 到本体的怪物 使用 T 攻击一次。 这时,N 最大化对体内怪物造成的总伤害。 找到 T 并输出总伤害。
但是,损坏 拥有 0 怪物是可以的。

文字列 x , 在|x| 是 x 表示长度。
文字列 x 和字符串 y , 在 x = y_i y_{i+1} … y_{i+l-1} (1 \leq i \leq |y|, 0 \leq l \leq |y|-i+1) 当 据说它是x 是 y 的子字符串。 然而 y_i (i = 1,…,|y|) 是 y 的 可以考虑 i 个字符。

入力形式

输入按以下格式给出。

N
S_1
…
S_N

一个整数,表示第一行的怪物数量。 给出 N 。
继续 N 每行都是代表怪物弱点的字符串。 给出 S_i ( i=1,…,N)。

出力形式

输出对怪物造成的总伤害的最大值。

制約

  • 1 \leq N \leq 10^5
  • S_i 是仅由小写字母 ('a',...,'z') 组成的非空字符串。
  • |S_1|+|S_2|+…+|S_N| \leq 10^5

针对该问题的判断设置了一组40分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。

  • N \leq 50

入出力例

入力例1

3
aab
ab
ac

出力例1

4

使用字符串“a”进行攻击 每个怪物的 1, 2, 3 每个到第二个怪物 1 造成伤害,总伤害为 3 。
使用字符串“ab”进行攻击 1, 2 每个到第二个怪物 2 造成伤害,总伤害为 4 。 此时,总伤害最大。

入力例2

2
abcde
cd

出力例2

5