TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1931
  • 题目
  • P1931【Trie】电话薄
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    何老板的手机很先进,当要拨打一个号码时,你需敲出该号码的前面几个数字,手机就会自动找出以该数字为前缀的所有号码。
    比如下列电话薄:
    TOM:1388
    JIM:13885599999
    LEE:13812345678
    TEC:0236588888
    如果何老板敲了138三个数字,手机屏幕上就会显示TOM、JIM和LEE的名字。很是方便呀!

    但是何老板发现有不好的地方就是比如他想拨打JIM的号码,当他在手机上敲了1388这四个数字,没等何老板敲完其它数字,手机就会自动拨打TOM的号码,这让何老板很是烦恼。也就是说一旦手机发现你当前敲出的数字与电话薄中的某个号码匹配了,它就会自动拨打该号码。

    于是何老板想知道,他的电话薄中,也就是是否存在一个号码是其它号码的前缀的情况。

    输入格式

    第一行,一个整数t,表示有t组测试数据1 ≤ t ≤ 40
    对于每组测试数据:
    第一行一个整数n(1 ≤ n ≤ 10000),表示电话薄中有n个号码
    接下来n行,每行一个数字,表示一个电话号码,每个电话号码的长度不超过10,并且是唯一的。

    输出格式

    每组测试数据输出一行,如果有有号码是其它号码的前缀,输出"NO"否则输出"YES"

    样例输入

    2
    4
    1388
    13885599999
    13812345678
    0236588888
    5
    113
    12340
    123440
    12345
    98346

    样例输出

    NO
    YES


    来源  改编自Nordic 2007 poj3630