Trie树
时间限制：1000MS 内存限制：131072KB
- 题目描述
给定N个01串，对于每一个01串，你需要判断：
1.如果它之前出现过，则输出之前最后出现的位置，否则
2.如果它是之前出现的某一01串的前缀，则输出0,否则
3.输出-1
- 输入格式
第一行一个数N
接下来N行每行一个01串
- 输出格式
共N行，每行一个数，见题目描述
- 样例输入
|
1 2 3 4 5 6 7 |
6 101 10 10 111 101 10 |
- 样例输出
|
1 2 3 4 5 6 |
-1 0 2 -1 1 3 |
- 数据规模与约定
0<=N<=10000，01串长度不超过100，文件大小不超过1M，并保证数据的梯度
看得出来，这个就是一个裸的字典树，每次先查询这个字符串在树中的位置，如果发现字符串的某一位指向一个未定义的节点就输出-1，否则输出对应节点的值。然后对这个字符串更新树，注意新增节点时把节点的值设为0，把树的尾部（字符串的结束）的节点的值设为当前字符串编号i，方便上面的查询输出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <cstdio> #include <cstring> #include <cstdlib> struct _node { _node*bz,*bo; int w; }st; void add(const int&w,const char s[]) { _node*t=&st; for(register int i=0;i<strlen(s);i++) if(s[i]=='0') { if(!t->bz) { t->bz=(_node*)malloc(sizeof(_node)); t->bz->w=0; t->bz->bz=NULL; t->bz->bo=NULL; } t=t->bz; } else if(s[i]=='1') { if(!t->bo) { t->bo=(_node*)malloc(sizeof(_node)); t->bo->w=0; t->bo->bz=NULL; t->bo->bo=NULL; } t=t->bo; } t->w=w; } void find(const char s[]) { _node*t=&st; for(register int i=0;i<strlen(s);i++) if(s[i]=='0') if(!t->bz) { printf("%d\n",-1); return; } else t=t->bz; else if(s[i]=='1') if(!t->bo) { printf("%d\n",-1); return; } else t=t->bo; printf("%d\n",t->w); } int main() { int N;scanf("%d",&N); for(register int i=1;i<=N;i++) { char s[10505]={0}; scanf("%s",s); find(s); add(i,s); } return 0; } |
