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