TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1930
  • Problem
  • P1930【Trie】最短前缀
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    有一字符串"carbon",它的子串"c", "ca", "car", "carb", "carbo", "carbon"称为它的前缀。也就是说一个字符串的前缀是指从该字符串最左边开始的子串。注意:空字符串不能被当作前缀,每个非空字符串本身也是它自己的前缀。

    在我们日常的口语中,我们很多时候都只说单词的前缀,而不是把整个单词都说完。比如:单词“carbohydrate”常常在口语中被说成“carb”。

    给你一些单词,你的任务是找出每个单词的最短前缀,要求不同的单词不能有相同的最短前缀。
    还有就是如果一个单词的前缀恰好是它本身,比如前缀"car"完全和单词"car"本身相同了,那么我们认为前缀"car"只能作为单词"car"的前缀,不能作为其它以"car"开始的单词比如"carriage"的前缀

    Input Format

    输入数据包含若干行(不超过1000行)
    每行是一个长度不超过20的单词。

    Output Format

    输出与输入有相同的行数
    每行为空格间隔的两个单词,第一个为原单词,第二个为该单词的最短前缀

    Sample Input

    carbohydrate
    cart
    carburetor
    caramel
    caribou
    carbonic
    cartilage
    carbon
    carriage
    carton
    car
    carbonate

    Sample Output

    carbohydrate carboh
    cart cart
    carburetor carbu
    caramel cara
    caribou cari
    carbonic carboni
    cartilage carti
    carbon carbon
    carriage carr
    carton carto
    car car
    carbonate carbona

    Hint

    感谢OBlack和rgnoH 提供数据


    Source  Rocky Mountain 2004