#P4494. [Neerc2013 North]heavy

    ID: 3729 传统题 1000ms 512MiB 尝试: 42 已通过: 7 难度: 6 上传者: 标签>难度分类提高图论二分图建模顶点覆盖Kuhn 算法由匹配构造最小点覆盖模拟与实现技巧时间戳避免清空数组CF2100

[Neerc2013 North]heavy

[NEERC2013 Northern] Heavy Chain Clusterization

题目描述

生物学家选出了 nn 个抗体样本。每个抗体用一个字符串表示它的重链,字符串中的每个大写英文字母代表一种氨基酸。

一组抗体可以构成一个相似群,当且仅当它们满足以下至少一个条件。

  • 该组所有字符串的前 kk 个字符相同。
  • 该组所有字符串的后 kk 个字符相同。

每个抗体必须归入恰好一个组。请将全部抗体分成尽可能少的相似群,输出最少组数。

输入格式

第一行输入两个正整数 n,kn,k。

接下来 nn 行,每行输入一个大写英文字母串,表示一个抗体的重链。每条重链长至少为 kk。

输出格式

输出一行一个整数,表示最少相似群数。

样例 1

4 1
AA
AB
BB
BA
2

一种划分是将第 1,21,2 个抗体分为一组,将第 3,43,4 个抗体分为一组。两组各自的前缀都相同。

样例 2

3 2
ABA
BAB
XY
3

三个抗体的前 22 个字符各不相同,后 22 个字符也各不相同,因此须分别成组。

数据范围

1≤n≤50001\le n\le5000,1≤k≤5501\le k\le550。本题库中的重链长度至多为 600600。