1247 hat’s words.cpp

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

#include <cstdio>
#include <string>
using namespace std;

/*字典树的数据结构*/

struct trie
{
	trie * next[26];
	bool exist[26];
};

/*字典树的相关操作*/

trie thead,*t,*s;

bool find(trie* head,char x[])
{
	int i;

	if(x[0]==0) return false;
   	s=head;
   	for(i=1; x[i] ;i++)
   	{
		if( s->next[ x[i-1]-'a' ] ) 
       		s=s->next[ x[i-1]-'a' ];
		else
			break;
   	}
	if(x[i]==0 && s->exist[ x[i-1]-'a' ]) 
		return true;
	else 
		return false;
}

void insert(trie *head,char x[])
{
	int i,j;

	if(x[0] == 0) return;
   	s=head;
   	for(i=1; x[i] ;i++)
   	{
		if( s->next[ x[i-1]-'a' ] ) 
			s=s->next[ x[i-1]-'a' ];
		else 
   		{
  			t=(trie*)malloc(sizeof(trie));
  			memset(t,0,sizeof(trie));
  			s->next[ x[i-1]-'a' ]=t;
  			s=t;
  		}
   	}//for
   	s->exist[ x[i-1]-'a' ]=true;
}

void deltrie(trie *current)
{
	int i;
	for(i=0;i<26;i++)
   	{
		if( current->next[i] ) 
			deltrie(current->next[i]);
	}
	free(current);
	current=NULL;
}

trie* inittrie()
{
	trie *head;
	
	head=(trie*)malloc(sizeof(trie));
	memset(head,0,sizeof(trie));
	return head;
}

/*字典树的相关操作*/

int total=0;
char dicword[50001][20];

int main()
{
	int i,j,len;
	char ch;
	trie * proot=inittrie();
	while( gets(dicword[total]) )
	{
		insert(proot,dicword[total]);
		total++;
	}
	for(i=0;i<total;i++)
	{
		for(j=1; dicword[i][j] ;j++)
		{
			ch=dicword[i][j];
			dicword[i][j]=0;
			if( find(proot,dicword[i]) )
			{
				dicword[i][j]=ch;
				if( find(proot,&dicword[i][j]) )
				{
					printf("%s\n", dicword[i]);
     				break;
				}
			}
			else
				dicword[i][j]=ch;
		}
	}
	deltrie(proot);
	return 0;
}