← 返回题目列表

Codeforces · 345/G

G. 后缀子组

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

给定一组 n 个字符串:s1、s2、...、sn。

您应该找到该群的子群 si1, si2, ..., sik (1 ≤ i1 < i2 < ... < ik ≤ n)。必须满足以下两个条件:

- 存在一个字符串 t,找到的子组中的每个字符串都是其后缀;
- 找到的子组中的字符串数量尽可能多。

您的任务是打印找到的子组中的字符串数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 组中字符串的数量。接下来的 n 行中的每一行都包含一个字符串。第 i 行包含非空字符串 si。

每个字符串仅由小写拉丁字母组成。所有字符串 si 的总和不超过 105。

输出

输出一个整数 — 找到的子组中的字符串数量。

示例

输入 #1

6
bb
bb
b
aaa
aa
z

输出 #1

3

注意

查看测试样本。所需的子组是 s1、s2、s3。