记录编号	32107	评测结果	AAAAAAAAAA
题目名称	[NOI 2000]单词查找树	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	1.036 s
提交时间	2011-11-05 14:27:14	内存使用	6.84 MiB

#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <memory.h>
using namespace std;

int n=0,c=1,len[100000]={0};
char word[100000][65]={{0}};

void swapint(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void swapallchar(int a,int b)
{
	int i,longer;
	char temp;
	if (len[a]>len[b])
		longer=len[a];
	else
		longer=len[b];
	for (i=0;i<longer;i++)
		if (word[a][i]!=word[b][i])
		{
			temp=word[a][i];
			word[a][i]=word[b][i];
			word[b][i]=temp;
		}
}

void qqsort(int l,int r)
{
	int i,ll,rr,temp;
	char str[65];
	memset(str,'@',sizeof(str));
	str[64]='\0';
	ll=l;
	rr=r;
	temp=rand()%(r-l+1)+l;
	for (i=0;i<len[temp];i++)
		str[i]=word[temp][i];
	while (ll<=rr)
	{
		while (strcmp(word[ll],str)<0)
			ll++;
		while (strcmp(str,word[rr])<0)
			rr--;
		if (ll<=rr)
		{
			if (ll!=rr)
			{
				swapint(len[ll],len[rr]);
				swapallchar(ll,rr);
			}
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

void solve(int l,int r,int dep)
{
	int ll,rr;
	char temp;
	ll=l;
	while (word[ll][dep]=='@')
		ll++;
	temp=word[ll][dep];
	while (ll<=r)
	{
		for (rr=ll+1;rr<=r;rr++)
			if (temp!=word[rr][dep])
				break;
		rr--;
		c++;
		solve(ll,rr,dep+1);
		ll=rr+1;
		temp=word[ll][dep];
	}
}

int main(void)
{
	freopen("trie.in","r",stdin);
	freopen("trie.out","w",stdout);
	memset(word,'@',sizeof(word));
	while (scanf("%s\n",word[n])==1)
	{
		len[n]=strlen(word[n]);
		word[n][len[n]]='@';
		word[n][64]='\0';
		n++;
	}
	qqsort(0,n-1);
	solve(0,n-1,0);
	printf("%d\n",c);
	fclose(stdin);
	fclose(stdout);
	return(0);
}