A7392 | 前二删一
时间限制3s
内存限制1024MB
通过 / 提交0/0
题目描述
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$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？