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分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码