← 返回题目列表

AtCoder · abc374_g

G. 只有一个产品名称

中文机器翻译题面 查看原题

分数: 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列表是由以下三个字符串组成的:

  • CABCDE
  • DF
  • XX

这有三个字符串,并且没有满足以下条件的 NG 列表 2 或更少的字符串,因此打印 3.


示例输入 2

5
AC
BC
CD
DE
DF

示例输出 2

2

满足条件的一个NG列表是由以下两个字符串组成的:

  • ACDE
  • BCDF

请注意,每个使用的产品名称可能出现在 NG 列表中的多个字符串中或在同一字符串中多次出现。


示例输入 3

6
AB
AC
CB
AD
DB
BA

示例输出 3

1

例如,NG 列表仅包含 ABACBADB 满足条件。