YZOJ T1860-P1 Trie树

Trie树

时间限制:1000MS 内存限制:131072KB

  • 题目描述

给定N个01串,对于每一个01串,你需要判断:

1.如果它之前出现过,则输出之前最后出现的位置,否则

2.如果它是之前出现的某一01串的前缀,则输出0,否则

3.输出-1

  • 输入格式

第一行一个数N

接下来N行每行一个01串

  • 输出格式

共N行,每行一个数,见题目描述

  • 样例输入

  • 样例输出

  • 数据规模与约定

0<=N<=10000,01串长度不超过100,文件大小不超过1M,并保证数据的梯度

 


 

看得出来,这个就是一个裸的字典树,每次先查询这个字符串在树中的位置,如果发现字符串的某一位指向一个未定义的节点就输出-1,否则输出对应节点的值。然后对这个字符串更新树,注意新增节点时把节点的值设为0,把树的尾部(字符串的结束)的节点的值设为当前字符串编号i,方便上面的查询输出。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注