HDu 3460(辞書ツリー)

http://acm.hdu.edu.cn/showproblem.php?pid=3460
最初は意味がわからなくて、長い間見ていて、やっと分かりました.単語を印刷してからプリンタの中でアルファベットを削除します.つまり、単語の接頭辞が同じであれば、単語の異なる部分を削除して、次の単語の異なる部分を挿入するだけです.このように、辞書ツリーを使って、単語の接頭辞が同じであれば、辞書ツリーに1つのノードしかありません.では、最も長い単語も削除すると、辞書ツリーのノードに1回挿入してもう一度削除し、n回出力します.つまり2*numnode+nです.しかし、最も長い単語lenは削除する必要はありません.2*numnode+n-lenです.

#include<iostream>

#include<cstring>

using namespace std;

typedef struct tree

{

	int num;

	tree *next[26];

}tree;

tree *root;

int count;

void creat(char str[])

{

	int len=strlen(str);

	tree *p=root,*q;

	for(int i=0;i<len;i++)

	{

		int x=str[i]-'a';

		if(p->next[x])

		{

			p->next[x]->num++;

			p=p->next[x];

		}

		else

		{

			q=(tree *)malloc(sizeof(tree));

			q->num=1;

			for(int j=0;j<26;j++)

				q->next[j]=NULL;

			p->next[x]=q;

			p=q;

			count++;

		}

	}

}

void del(tree *p)

{

	for(int i=0;i<26;i++)

	{

		if(p->next[i])

			del(p->next[i]);

	}

	free(p);

}

int main()

{

	int n;

	while(scanf("%d",&n)>0)

	{

		root=(tree *)malloc(sizeof(tree));

		for(int j=0;j<26;j++)

			root->next[j]=NULL;

		root->num=0;

		char s[50];

		int i,max=0,len;

		count=0;

		for(i=0;i<n;i++)

		{

			scanf("%s",s);

			creat(s);

			len=strlen(s);

			if(len>max)

				max=len;

		}

		printf("%d
",2*count+n-max);

		del(root);

	}

	return 0;

}