F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5032. -- [Jsoi2014]病毒分类

5032: [Jsoi2014]病毒分类

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 24  Solved: 1
[Submit][Status][Discuss]

Description

JSOI爆发一种罕见的懒惰拖延症,为了拯救小伙伴们于水生火热之中,
JYY 收集了 JSOI王国中所有病毒的DNA序列,并希望对这些DNA序列进行分类, 
以便深入分析来找出治疗拖延症的方法。
JSOI王国里一共有N种不同的病毒,每种病毒的DNA序列都由一个大写字母序列来表示。
JYY希望将这些病毒分成尽量少的类别,使得每个病毒都属于且仅属于某一个类别。
分入同一个类别的病毒需要满足如下两条性质中的至少一条:
1、 所有同类病毒DNA序列的“k前缀”(前k个大写字母)都相同;
2、 所有同类病毒DNA序列的“k后缀”(后k个大写字母)都相同。
JYY希望找出一种分类方案,使得所分成的类别满足要求并且类别总数最小。

Input

第一行包含两个正整数 N 和 k 。
接下来 N 行,第 i 行包含一个字符串 Si ,表示编号为 i 的病毒的 DNA 序列 。
数据保证 Si 的长度不小于 k 。
N≤5000 & k≤550 & k≤|Si|≤600

Output

第一行包含一个整数 C ,表示最少的类别的数量。
接下来 C 行,每一行首先为一个正整数 w ,表示当前类别中的病毒数量,
接下来 w 个正整数,表示属于当前类别的病毒的编号。
如果有多个最佳方案,输出任意一组即可。

Sample Input

4 1
A
AB
BB
BA

Sample Output

2
2 1 2
2 3 4

HINT

Source

Round3

[Submit][Status][Discuss]

HOME Back