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

struct node1
{
	char c;
	int isleaf;
	int count;
	struct node1 *left;
	struct node1 *right;
}node[26];

int find(char t[30])
{
	struct node1 *p,*p1,*p2;
	int i,len;
	len=strlen(t);
	p=&node[t[0]-'a'];
	for(i=1;i<len;i++)
	{
		p=p->left;
		while(1)
		{
			if(p->c==t[i])
			{
				if(p->isleaf&&i==len-1)return i;
				if(p->count==1)return i;
				break;
			}
			p=p->right;
		}
	}

}

void insert(char *t)
{
	struct node1 *p,*p1,*p2;
	int i,len;
	len = strlen(t);
	p=&node[t[0]-'a'];
	p->count++;
	for(i=1;i<len;i++)
	{
		if(p->left==NULL)
		{
			p->left=(struct node1 *)malloc(sizeof(struct node1));
			p=p->left;
			p->c=t[i];
			p->right=NULL;p->left=NULL;p->isleaf=0;p->count=1;
			continue;
		}
		p=p->left;
		while(1)
		{
			if(p->c==t[i])
			{
				p->count++;
				break;
			}
			else if(p->right==NULL)
			{
				p->right=(struct node1 *)malloc(sizeof(struct node1));
				p=p->right;
				p->c=t[i];
				p->right=NULL;p->left=NULL;p->isleaf=0;p->count=1;
				break;
			}
			else p=p->right;
		}
	}
	p->isleaf=1;
}

void init()
{
	int i;
	for(i=0;i<26;i++)
	{
		node[i].c=i+'a';
		node[i].isleaf=0;
		node[i].count=0;
		node[i].left=NULL;
		node[i].right=NULL;
	}
}

int main()
{
	char s[1000][30];
	int i,j,k,lim=0,t;
	init();
	while(gets(s[lim]))
	{
        if(strlen(s[lim])<1)break;
		insert(s[lim]);
		lim++;
	}
	for(i=0;i<lim;i++)
	{
		j = find(s[i]);
		printf("%s ",s[i]);
		for(k=0;k<=j;k++)
			putchar(s[i][k]);
		putchar('\n');
	}
	return 0;
}

• 错了一个小地方 (1843) yiyiyi4321 2006-08-17 18:05:09