#P4494. [Neerc2013 North]heavy
[Neerc2013 North]heavy
[NEERC2013 Northern] Heavy Chain Clusterization
题目描述
生物学家选出了 个抗体样本。每个抗体用一个字符串表示它的重链,字符串中的每个大写英文字母代表一种氨基酸。
一组抗体可以构成一个相似群,当且仅当它们满足以下至少一个条件。
- 该组所有字符串的前 个字符相同。
- 该组所有字符串的后 个字符相同。
每个抗体必须归入恰好一个组。请将全部抗体分成尽可能少的相似群,输出最少组数。
输入格式
第一行输入两个正整数 。
接下来 行,每行输入一个大写英文字母串,表示一个抗体的重链。每条重链长至少为 。
输出格式
输出一行一个整数,表示最少相似群数。
样例 1
4 1
AA
AB
BB
BA
2
一种划分是将第 个抗体分为一组,将第 个抗体分为一组。两组各自的前缀都相同。
样例 2
3 2
ABA
BAB
XY
3
三个抗体的前 个字符各不相同,后 个字符也各不相同,因此须分别成组。
数据范围
,。本题库中的重链长度至多为 。