HDU-1800-Flying to the Mars

HDU-1800-Flying to the Mars

http://acm.hdu.edu.cn/showproblem.php?pid=1800

字典树，每一个节点有10个叶子节点，注意前缀的0要去掉

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Max;
struct node
{
	int count;
	node *childs[10];
	node()
	{
		count=0;
		int i;
		for(i=0;i<=9;i++)
		childs[i]=NULL;
	}
};
node *root,*current,*newnode;
void insert(char *str)
{
	int i,m;
	current=root;
	for(i=0;i<strlen(str);i++)
	{
		m=str[i]-'0';
		if(current->childs[m]!=NULL)
		current=current->childs[m];
		else
		{
			newnode=new node;
			current->childs[m]=newnode;
			current=newnode;
		}
	}
	++(current->count);
	if((current->count)>Max)
	Max=(current->count);
}
int main()
{
	int n,i,len;
	char s[40],str[40];
	while(scanf("%d",&n)!=EOF)
	{
		Max=-1;
		root=new node;
		while(n--)
		{
			scanf("%s",s);
			len=strlen(s);
			for(i=0;i<len-1;i++)
			if(s[i]!='0')
			break;
			if(i==len-1)
			{
				str[0]=s[len-1];
			    str[1]='\0';
			}
			else
			{
				strncpy(str,&s[i],len-i); 
				str[len-i]='\0';
			}
		    insert(str);
		}
		printf("%d\n",Max);
	}
	return 0;
}