| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
发一下我丑陋的Trie,惩罚一下自己#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator