#P3395. [Usaco2006 Feb]Cellphones 手机
[Usaco2006 Feb]Cellphones 手机
题目描述
奶牛的名字由英文字母表的前 个大写字母组成。把这 个字母从小到大分成 段,每一段非空且字母连续。第 段的字母都由第 个按键输入。
一个名字对应一个按键编号序列。如果词典里只有这一个名字对应此序列,它就能被唯一识别。请安排各按键上的字母,使可唯一识别的名字尽量多。
输入格式
本站数据第一行有一个整数,表示测试点编号。读入后忽略它。
第二行两个整数 ()。第三行一个整数 (),表示词典里的名字数。
接下来 行,每行一个长度为 至 的大写字母串,字母均在给定的前 个字母之内。名字按字典序给出,互不相同。
输出格式
第一行输出能唯一识别的名字的最大数量。随后输出 行,第 行按字母序列出第 个按键的所有大写字母。
如有多种最优方案,先选第 个按键容纳字母最多的方案。如仍并列,比较第 个按键的字母数量,依次类推。
样例
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK
7
AB
CDEFGHIJK
LM
样例说明
四个名字 CELL、DILL、FILL 和 FILM 都对应按键序列 ,其余七个名字均可唯一识别。