P1930【Trie】最短前缀 | |
|
问题描述
有一字符串"carbon",它的子串"c", "ca", "car", "carb", "carbo", "carbon"称为它的前缀。也就是说一个字符串的前缀是指从该字符串最左边开始的子串。注意:空字符串不能被当作前缀,每个非空字符串本身也是它自己的前缀。
在我们日常的口语中,我们很多时候都只说单词的前缀,而不是把整个单词都说完。比如:单词“carbohydrate”常常在口语中被说成“carb”。
给你一些单词,你的任务是找出每个单词的最短前缀,要求不同的单词不能有相同的最短前缀。
还有就是如果一个单词的前缀恰好是它本身,比如前缀"car"完全和单词"car"本身相同了,那么我们认为前缀"car"只能作为单词"car"的前缀,不能作为其它以"car"开始的单词比如"carriage"的前缀
输入格式
输入数据包含若干行(不超过1000行)
每行是一个长度不超过20的单词。
输出格式
输出与输入有相同的行数
每行为空格间隔的两个单词,第一个为原单词,第二个为该单词的最短前缀
样例输入
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
样例输出
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
提示
感谢OBlack和rgnoH 提供数据
来源 Rocky Mountain 2004