`
xinjiang
  • 浏览: 55467 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

POJ 2001 Shortest Prefixes

阅读更多

Description

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", "car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate" is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo".

An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car" , not for "carriage" or any of the other words in the list that begins with "car".

Input

The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

Output

The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.

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

 

解题思路:使用 trie 树结构。在 trie 树节点中加入两个域count[] next 。count[i] 表示有多少个单词经过这个节点。先将所有单词保存在 trie 树中,然后一个一个地查找,当到达某个节点使用 count[i] ==1 ,那么从根到该节点组成的字符串便是该单词的最短前缀。

#include <stdio.h>
#include <malloc.h>
#include <string.h>

int t = 0;
typedef struct Trie
{
    int count[26];   //统计该字符出现的次数
    struct Trie *next[26];  //26个字母,开辟26个空间
} Trie;


void initTire(Trie *root, char *string)
{
    Trie *trie = root;    //根节点不含有数据,只有26个指针域
    int i;
    int j;

    while(*string != '\0')
    {
        j = *string-'a';
        if(trie->next[j] == NULL)
        {
            trie->next[j] = (Trie *)malloc(sizeof(Trie));
            (trie->next[j])->count[j] = 1;
            trie = trie->next[j];
            for(i = 0; i < 26; i++)
            {
                trie->next[i] = NULL;
            }
        }
        else
        {
            (trie->next[j])->count[j]++;
            trie = trie->next[j];
        }
        string++;
    }
}

void findPrefix(Trie *root, char *string)
{
    //寻找前缀
    Trie *trie = root;
    int i = 0, j;


    while(*string != '\0')
    {
        j = *string-'a';
        if((trie->next[j])->count[j] == 1)
        {
            //如果当前字母只出现一次,证明前缀字母到此结束
            printf("%c", *string);
            break;
        }
        printf("%c", *string);
        trie = trie->next[j];
        string++;
    }
}

int main()
{
    int i = 0;
    int n;
    char str[3000][21];
    char *pre;
    Trie *root;

    root = (Trie *)malloc(sizeof(Trie));
    for(i = 0; i < 26; i++)
    {
        root->next[i] = NULL;
    }

    i = 0;
    while(scanf("%s", str[i]) != EOF)
    {
        initTire(root, str[i]);
        getchar();
        i++;
    }

    n = i;
    for(i = 0; i < n; i++)
    {
        printf("%s ", str[i]);
        findPrefix(root, str[i]);
        printf("\n");
    }
    return 0;
}
 
分享到:
评论

相关推荐

    poj 3554 Almost the shortest route.md

    poj 3554 Almost the shortest route.md

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

    poj 3414解题报告

    poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    poj 1012解题报告

    poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告

    poj 2329解题报告

    poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告

    poj 1659解题报告

    poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告

    POJ1503解答,正确答案(已通过POJ)

    POJ1503解答 POJ1503解答,正确答案(已通过POJ)

Global site tag (gtag.js) - Google Analytics