A7681. [AGC047B] First Second
编程题
普及+/提高
知识点
题目描述
Limak 可以反复执行以下操作：从字符串的前两个字符中去掉其中一个。例如，$abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx$。
给定 $N$ 个互不相同的字符串 $S_1, S_2, \ldots, S_N$。在所有 $N \cdot (N-1) / 2$ 个无序对 $(S_i, S_j)$ 中，有多少对满足リマク可以通过上述操作从一个字符串得到另一个字符串？
给定 $N$ 个互不相同的字符串 $S_1, S_2, \ldots, S_N$。在所有 $N \cdot (N-1) / 2$ 个无序对 $(S_i, S_j)$ 中，有多少对满足リマク可以通过上述操作从一个字符串得到另一个字符串？
输入格式
输入以如下格式从标准输入读入。
> $N$
> $S_1$
> $S_2$
> $\vdots$
> $S_N$
> $N$
> $S_1$
> $S_2$
> $\vdots$
> $S_N$
输出格式
输出满足 Limak 可以从一个字符串得到另一个字符串的无序对 $(S_i, S_j)$（$i \neq j$）的个数。
输入输出样例
输入 #1
3 abcxyx cyx abc
输出 #1
1
输入 #2
6 b a abc c d ab
输出 #2
5
说明/提示
## 限制条件
- $2 \leq N \leq 200\,000$
- $S_i$ 由小写英文字母
- $S_i \neq S_j$
- $1 \leq |S_i|$
- $|S_1| + |S_2| + \ldots + |S_N| \leq 10^6$
## 样例解释 1
满足条件的对只有 $(abcxyx, cyx)$。
## 样例解释 2
满足条件的对有 $(b, abc)$、$(a, abc)$、$(abc, c)$、$(b, ab)$、$(a, ab)$，共 $5$ 对。
- $2 \leq N \leq 200\,000$
- $S_i$ 由小写英文字母
a - z 组成。- $S_i \neq S_j$
- $1 \leq |S_i|$
- $|S_1| + |S_2| + \ldots + |S_N| \leq 10^6$
## 样例解释 1
满足条件的对只有 $(abcxyx, cyx)$。
## 样例解释 2
满足条件的对有 $(b, abc)$、$(a, abc)$、$(abc, c)$、$(b, ab)$、$(a, ab)$，共 $5$ 对。