#P3395. [Usaco2006 Feb]Cellphones 手机

[Usaco2006 Feb]Cellphones 手机

题目描述

奶牛的名字由英文字母表的前 LL 个大写字母组成。把这 LL 个字母从小到大分成 BB 段,每一段非空且字母连续。第 ii 段的字母都由第 ii 个按键输入。

一个名字对应一个按键编号序列。如果词典里只有这一个名字对应此序列,它就能被唯一识别。请安排各按键上的字母,使可唯一识别的名字尽量多。

输入格式

本站数据第一行有一个整数,表示测试点编号。读入后忽略它。

第二行两个整数 B,LB,L(1≤B≤L≤261\le B\le L\le26)。第三行一个整数 DD(1≤D≤10001\le D\le1000),表示词典里的名字数。

接下来 DD 行,每行一个长度为 11 至 1010 的大写字母串,字母均在给定的前 LL 个字母之内。名字按字典序给出,互不相同。

输出格式

第一行输出能唯一识别的名字的最大数量。随后输出 BB 行,第 ii 行按字母序列出第 ii 个按键的所有大写字母。

如有多种最优方案,先选第 11 个按键容纳字母最多的方案。如仍并列,比较第 22 个按键的字母数量,依次类推。

样例

1
3  13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK
7
AB
CDEFGHIJK
LM

样例说明

四个名字 CELL、DILL、FILL 和 FILM 都对应按键序列 2,2,3,32,2,3,3,其余七个名字均可唯一识别。

题目来源