【统计偏题】 hdu1251

【统计难题】 hdu1251

看了这个题目，统计难题，但一读题，原来是个关于Trie字典树的运用，完全是根据Trie算法，是一个模版题。

#include <iostream>
#include <string.h>
using namespace std;

const  int sonsum=26,base='a';
char s1[12],ss[12];

struct Trie
{
	int num;
	bool flag;
	struct Trie *son[sonsum];
	Trie()
	{
		num=1;flag=false;
		memset(son,NULL,sizeof(son));
	}
};

Trie *NewTrie()
{
	Trie *temp=new Trie;
	return temp;
}

void Inset(Trie *root,char *s)
{
	Trie *temp=root;
	while(*s)
	{
		if(temp->son[*s-base]==NULL)
		{
			temp->son[*s-base]=NewTrie();
		}
		else
		    temp->son[*s-base]->num++;
        temp=temp->son[*s-base];
        s++;
	}
	temp->flag=true;
}

int search(Trie *root,char *s)
{
	Trie *temp=root;
	while(*s)
	{
		if(temp->son[*s-base]==NULL) return 0;
		temp=temp->son[*s-base];
		s++;		
	}
	return temp->num;
}


int main()
{
	Trie *root=NewTrie();
	root->num=0;
	//while(cin.get(s1,12))
	while(gets(s1)&&strcmp(s1,"")!=0)  
	{
		//if(strcmp(s1," ")==0)
		//break;
		Inset(root,s1);
	}
	while(cin>>ss)
	{
		int  ans=search(root,ss);
		cout<<ans<<endl;
	}
	
	
	return 0;
}