CF1483F Exam

今年木叶村再次举办中忍选拔考试，参加考试的有 $n$ 名忍者，名字分别为 $s_1$、$s_2$、…、$s_n$。所有名字都互不相同。考试的一个环节是忍者之间的对决。今年决定对决双方的规则如下：如果满足以下条件，忍者 $i$ 和忍者 $j$ 将进行对决： - $i \neq j$； - $s_j$ 是 $s_i$ 的子串； - 不存在除 $i$ 和 $j$ 以外的 $k$，使得 $s_j$ 是 $s_k$ 的子串，且 $s_k$ 是 $s_i$ 的子串。 如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的子串。 你的任务是计算今年将会有多少场对决。

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示考生人数。 接下来的 $n$ 行，每行一个字符串，表示他们的名字。没有两个名字相同，所有名字均为非空且仅包含小写英文字母。所有名字的总长度不超过 $10^6$。

输出一个整数，表示对决的场数。

在第一个样例中，hidan 会和 dan 对决，hanabi 会和 nabi 对决，nabi 也会和 bi 对决。hanabi 和 bi 不会对决，因为存在名为 nabi 的忍者，满足第三个条件。 在第二个样例中，abacaba 和 acaba、abacaba 和 abaca、acaba 和 aca、abaca 和 aca 之间会进行对决。 由 ChatGPT 4.1 翻译