分数: 600 点
问题陈述
所有 KEYENCE 产品名称均包含以下内容 两个大写英文字母.
他们已经使用过 N 产品名称, i- 其中 (1\leq i\leq N) is S_i.
产品名称一旦使用,就无法重复使用,因此他们决定创建一个 NG(不好)列表,以快速识别以前使用过的产品名称。
NG 列表必须满足以下条件。
- 由一个或多个字符串组成,每个字符串由大写英文字母组成。
- 对于每个已使用的产品名称,列表中至少存在一个包含该名称作为(连续)子字符串的字符串。
- 列表中的字符串都不包含任何长度-2 (连续)子字符串,不是已使用的产品名称。
找出 NG 列表中可能的最小字符串数。
约束
- 1\leq N\leq 26^2
- N 是一个整数。
- 每个 S_i 是一个长度为的字符串 2 由大写英文字母组成。
- 全部 S_1,S_2,\ldots,S_N 是不同的。
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
打印 NG 列表中可能的最小字符串数。
示例输入 1
7 AB BC CA CD DE DF XX
示例输出 1
3
满足条件的一个NG列表是由以下三个字符串组成的:
CABCDEDFXX
这有三个字符串,并且没有满足以下条件的 NG 列表 2 或更少的字符串,因此打印 3.
示例输入 2
5 AC BC CD DE DF
示例输出 2
2
满足条件的一个NG列表是由以下两个字符串组成的:
ACDEBCDF
请注意,每个使用的产品名称可能出现在 NG 列表中的多个字符串中或在同一字符串中多次出现。
示例输入 3
6 AB AC CB AD DB BA
示例输出 3
1
例如,NG 列表仅包含 ABACBADB 满足条件。