A7392. 前二删一
编程题
普及+/提高
知识点
题目描述
Limak 有一个字符串，他可以反复执行下面的操作：
从当前字符串的前两个字符中，选择一个字符删除。
例如：
$$ abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx $$
现在给定 $N$ 个互不相同的字符串 $S_1,S_2,\dots,S_N$。
对于一对不同的字符串 $(S_i,S_j)$，如果 Limak 可以通过若干次上述操作，把其中一个字符串变成另一个字符串，那么这一对字符串就是一对合法字符串。
请你求出合法字符串对的数量。
注意：
字符串对是无序的，也就是说 $(S_i,S_j)$ 和 $(S_j,S_i)$ 只算一对。
由于每次操作都会删除一个字符，所以只有较长的字符串可能变成较短的字符串。
从当前字符串的前两个字符中，选择一个字符删除。
例如：
$$ abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx $$
现在给定 $N$ 个互不相同的字符串 $S_1,S_2,\dots,S_N$。
对于一对不同的字符串 $(S_i,S_j)$，如果 Limak 可以通过若干次上述操作，把其中一个字符串变成另一个字符串，那么这一对字符串就是一对合法字符串。
请你求出合法字符串对的数量。
注意：
字符串对是无序的，也就是说 $(S_i,S_j)$ 和 $(S_j,S_i)$ 只算一对。
由于每次操作都会删除一个字符，所以只有较长的字符串可能变成较短的字符串。
输入格式
第一行输入一个整数 $N$，表示字符串的数量。
接下来 $N$ 行，每行输入一个字符串 $S_i$。
接下来 $N$ 行，每行输入一个字符串 $S_i$。
输出格式
输出一个整数，表示合法字符串对的数量。
输入输出样例
输入 #1
3 abcxyx cyx abc
输出 #1
1
输入 #2
6 b a abc c d ab
输出 #2
5
说明/提示
样例解释 2
满足条件的字符串对有：
$$ (b,abc),(a,abc),(abc,c),(b,ab),(a,ab) $$
共 $5$ 对。
例如：
$abc \rightarrow bc \rightarrow b$，所以 $(b,abc)$ 合法；
$abc \rightarrow ac \rightarrow a$，所以 $(a,abc)$ 合法；
$abc \rightarrow bc \rightarrow c$，所以 $(abc,c)$ 合法；
$ab \rightarrow b$，所以 $(b,ab)$ 合法；
$ab \rightarrow a$，所以 $(a,ab)$ 合法。
数据范围
对于所有测试数据，满足：
- $2\le N\le 200000$
- $S_i$ 仅由小写英文字母 a 到 z 组成
- 任意两个字符串互不相同
- $1\le |S_i|$
- $\sum |S_i|\le 10^6$
满足条件的字符串对有：
$$ (b,abc),(a,abc),(abc,c),(b,ab),(a,ab) $$
共 $5$ 对。
例如：
$abc \rightarrow bc \rightarrow b$，所以 $(b,abc)$ 合法；
$abc \rightarrow ac \rightarrow a$，所以 $(a,abc)$ 合法；
$abc \rightarrow bc \rightarrow c$，所以 $(abc,c)$ 合法；
$ab \rightarrow b$，所以 $(b,ab)$ 合法；
$ab \rightarrow a$，所以 $(a,ab)$ 合法。
数据范围
对于所有测试数据，满足：
- $2\le N\le 200000$
- $S_i$ 仅由小写英文字母 a 到 z 组成
- 任意两个字符串互不相同
- $1\le |S_i|$
- $\sum |S_i|\le 10^6$