TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1930
  • 题目
  • P1930【Trie】最短前缀
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    有一字符串"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