TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1931
  • Problem
  • P1931【Trie】电话薄
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

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

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

    Input Format

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

    Output Format

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

    Sample Input

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

    Sample Output

    NO
    YES


    Source  改编自Nordic 2007 poj3630