boj 376

Description
cloudiris是个爱学习的好孩子，每天她都会记单词，可她一翻开单词书看到如此之多的单词就感到头疼，于是她想出了一个和别人不相同的记单词的方法。她把单词归类分成几组，每一组单词的开头几个字母都是相同的，现在她需要根据给出的这组单词找出每个单词的最短前缀来唯一的标识这个单词。例如： carburetor 和carbohydrate 的最短前缀分别是carbu和carbo ，而carburetor 和car的最短前缀分别是carb和car

Input
一组单词 ，每个单词一行，一共不超过1000行，每个单词由不超过20个小写字母组成，没有两个单词完全相同。

Output
对应于每个单词输出此单词的最短前缀,一个前缀一行。

Sample Input

carbohydrate
cart
carburetor
caramel
caribou

Sample Output

carbo
cart
carbu
cara
cari

Source
dreamzk

 

字典树，先建树，然后在对于每个单词，从树的根节点开始向下遍历单词所在路径，如果单词中某个字母只出现一次，则从第0层到此层为此单词的前缀，否则前缀为单词本身

代码：

 

#include<iostream>
using namespace std;

#define Max 26
#define N 50000

char a[1005][26];
struct TrieNode{
	int nCount;
	TrieNode *next[Max];
};
TrieNode Memory[N];
int allocNum=0;
TrieNode *NewNode()
{
	TrieNode *tmp=&Memory[allocNum++];
	for(int i=0;i<Max;i++)
		tmp->next[i]=NULL;
	tmp->nCount=0;
	return tmp;
}

void InsertString(TrieNode *root,char *s)
{
	int len=strlen(s);
	TrieNode *tmp=root;
	for(int i=0;i<len;i++)
	{
		if(tmp->next[s[i]-'a']==NULL)
			tmp->next[s[i]-'a']=NewNode();
		tmp->next[s[i]-'a']->nCount++;
		tmp=tmp->next[s[i]-'a'];
	}
}

void FindPrefix(TrieNode *root,char *s)
{
	int len=strlen(s);
	TrieNode *tmp=root;
	for(int i=0;i<len;i++)
	{
		printf("%c",s[i]);
		if(tmp->next[s[i]-'a']->nCount==1)
			break;
		tmp=tmp->next[s[i]-'a'];
	}
	printf("\n");
}

int main()
{
	int cnt=0;
	TrieNode *root=NewNode();
	while(~scanf("%s",&a[cnt]))
		InsertString(root,a[cnt++]);
	for(int i=0;i<cnt;i++)
		FindPrefix(root,a[i]);
}