Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

发一下我丑陋的Trie,惩罚一下自己

Posted by proverbs at 2012-07-10 20:53:22 on Problem 3630
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define N 100010
using namespace std;
struct TRIE
{
	int son[11];
}trie[N];
char a[N][15];
int len,b[15],num,m;
void initial()
{
	for(int i=0;i<=9;i++)
	   trie[0].son[i]=-1;
	num=0;
}
void insert()
{
	int now=0;
	for(int i=1;i<=len;i++)
	{
		if(trie[now].son[b[i]]==-1)
		{
			num++;
			for(int j=0;j<=9;j++)
			   trie[num].son[j]=-1;
			trie[now].son[b[i]]=num;
		}
		now=trie[now].son[b[i]];
	}
}
bool check(int x)
{
	for(int i=0;i<=9;i++)
		if(trie[x].son[i]!=-1) return true;
	return false;
}
bool find(int k)
{
	int now=0;
	len=strlen(a[k]+1);
	for(int i=1;i<=len;i++)
	{
		now=trie[now].son[a[k][i]-'0'];
		if(now==-1) return false;
	}
	if(check(now)) return true;
	return false;
}
void go()
{
	for(int i=1;i<=m;i++)
		if(find(i)) {printf("NO\n");return;}
	printf("YES\n");
}

int main()
{
	int tt;
	scanf("%d",&tt);
	while(tt--)
	{
		initial();
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%s",a[i]+1);
			len=strlen(a[i]+1);
			for(int j=1;j<=len;j++)
			   b[j]=a[i][j]-'0';
			insert();
			
		}
		go();
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator