pku2001

额，比较简单的字典树，找出一个单词最短而且唯一的前缀，就是不会跟其他单词重复

这样的话，插入只需在每一个单词经过的路径的节点p->v上累加，查找时，检查p->v的值，当p->==1时，即到此节点为止的前缀是最短而且是唯一的

不知道大牛的0ms是怎么做出来的，，我用了16ms，膜拜啊

#include<iostream>
#include<string>
using namespace std;
struct node
{
	node *next[26];
	int v;
};
node *root;
char str[1001][21];
void insert(char *s)
{
	node *p=root;
	for(;*s!='\0';s++)
	{
		int d=*s-'a';
		if(p->next[d]!=NULL)
			p->v++;
		else 
			{
				p->next[d]=new node();
				p->v++;
		}
		p=p->next[d];
	}
	p->v++;
}
void find(char *s)
{
	node *p=root;
	char *s1=s;
	for(;*s1!='\0';s1++)
	{
		int d=*s1-'a';
		p=p->next[d];
		//cout<<p->v<<endl;
		if(p->v==1)
		{
			*(++s1)='\0';
			cout<<s<<endl;
			return ;
		}
	}
	cout<<s<<endl;
}
int main()
{
	int i=0;
	root=new node();
	while(scanf("%s",str[i])!=EOF)
	{
		insert(str[i]);
		i++;
	}
	for(int j=0;j<i;j++)
	{
		cout<<str[j]<<' ';
		find(str[j]);
	}
	return 0;
}