1799:最短前缀（4.6算法之贪心）

1799:最短前缀

总时间限制: 1000ms 内存限制: 65536kB
描述
一个字符串的前缀指的是从该字符串首字符开始的一段连续字符序列。例如，“carbon”所包含的前缀包括： “c”, “ca”, “car”, “carb”, “carbo”以及“carbon”。需要注意的是，此处不将空字符串视为有效前缀，但每一个非空字符串本身均可作为自身的前缀。目前我们希望借助前缀的方式来对单词进行缩略表达。例如，“carbohydrate”通常可以被简化为“carb”。现在给定一组单词，要求找出能够唯一标识每个单词的最短前缀。
在以下示例中，“carbohydrate”可以被简化为“carboh”，但无法被简化为“carbo”（或其他更短的前缀），因为已有另一个单词以“carbo”作为开头。精确匹配具有优先权，例如，当存在一个单词与某个前缀完全一致时，该匹配将覆盖其他可能的前缀匹配。因此，“car”作为“car”的缩略形式是无歧义的，并不会与其他以“car”开头的单词如“carriage”产生混淆。
输入
输入内容包含至少2行、最多1000行文本。每行文本由一个仅由小写字母组成的单词构成，且每个单词长度不少于1个字符、不超过20个字符。
输出
输出行数与输入行数相等。每一行输出均以对应输入行中的单词开头，随后接一个空格及该单词对应的无歧义最短