1251 统计难题.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//字典树，也称为键树，属于多路查找树 
#include <cstdio>
#include <string>
using namespace std;

struct trie
{
	trie * next[26];
	int all;
};
trie *thead;

inline trie * newnode()
{
	int i;
	
	trie *t;
	t=(trie*)malloc(sizeof(trie));
	memset(t,0,sizeof(trie));
	return t;
}
void insert(trie * s,char x[])
{
	int i;
	trie *t;
	
	for(i=0; x[i] ; i++)
	{
		if( s->next[ x[i]-'a' ] )
		{
			s=s->next[ x[i]-'a' ];
		}
		else
		{
			t=newnode();
			s->next[ x[i]-'a' ]=t;
			s=t;
		}
		s->all++;
	}//for
}
void deltrie(trie * s)
{
	int i;
	
	for(i=0;i<26;i++)
   	{
		if( s->next[i] ) 
			deltrie(s->next[i]);
	}
	free(s);
	s=NULL;
}
int find(trie *s,char x[])
{
	int i;
	
	if(x[0]==0)
		return -1;
	for(i=0; x[i] ; i++)
	{
		if( s->next[ x[i]-'a' ] )
			s=s->next[ x[i]-'a' ];
		else
			break;	
	}
	if(x[i]==0)
		return s->all;
	else
		return 0;
}

int main()
{
	int i,t;
	char word[11];
	
	thead=newnode();
	while( gets(word) )
	{
		if(word[0]==0)
			break;
		insert(thead,word);	
	}
	while( gets(word) )
	{
		t=find(thead,word);
		printf("%d\n",t);
	}
	deltrie(thead);
	return 0;
}