poj 3630 trie
2010年9月22日 17:53
刚接触trie树,试着做做,写的好挫。。。
Trie(from维基百科)
Trie 又称单词查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
性质 它有3个基本性质:
- 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
#include <cstdio> #include <cstring> #define NODEMAX 100005 struct node { int next[10]; int key; } trie[NODEMAX]; int nodeindex=1; bool search(char word[]) { int i=0,t,in=0;//root while(word[i]!='\0') { t=word[i]-'0'; if(trie[in].next[t]==0) { memset(trie[nodeindex].next,0,sizeof(trie[nodeindex].next)); trie[nodeindex].key=0; trie[in].next[t]=nodeindex++; } in=trie[in].next[t]; if(word[i+1]=='\0'&&trie[in].key>0) return true; if(word[i+1]!='\0'&&trie[in].key==2) return true; trie[in].key=1; i++; } trie[in].key=2; return false; } int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout); #endif int cas;scanf("%d",&cas); int n,i; char num[11]; bool failed; while(cas--) { scanf("%d",&n); memset(trie[0].next,0,sizeof(trie[0].next)); trie[0].key=0; failed=0;nodeindex=1; for(i=0;i<n;i++) { scanf("%s",num); if(!failed&&search(num)) failed=1; } if(!failed) puts("YES"); else puts("NO"); } }