题目描述

给出一个电话列表，如果列表中存在其中一个号码是另一个号码的前缀这一情况，那么就称这个电话列表是不兼容的。

假设电话列表如下：

· Emergency 911
· Alice 97 625 999
· Bob 91 12 54 26

在此例中，报警电话号码（911）为Bob电话号码（91 12 54 26）的前缀，所以该列表不兼容。

输入格式
第一行输入整数t，表示测试用例数量。

对于每个测试用例，第一行输入整数n，表示电话号码数量。

接下来n行，每行输入一个电话号码，号码内数字之间无空格，电话号码不超过10位。

输出格式
对于每个测试用例，如果电话列表兼容，则输出”YES”。

否则，输出”NO”。

数据范围
$1≤t≤40$
$1≤n≤10000$

样例

输入样例：
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
输出样例：
NO
YES

字典树

这道题目我们的重点,就是前缀,其他部分均和普通字典树一样,那么我们如何去处理这个前缀呢,其实就可以暴力枚举即可,也就是每一个串,都取出它的前缀,然后check这个前缀出现没有.如果出现过了,那么就是不合法的.

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int Len=1e5+10;
char st[10100][10];
int End[Len],trie[Len][10],tot;
void init()
{
    tot=1;
    memset(trie[0],0,sizeof(trie[0]));
    memset(End,0,sizeof(End));
}
void insert(char *s)
{
    int len=strlen(s),p=0;
    fir(i,0,len-1)
    {
        int ch=s[i]-'0';
        if(!trie[p][ch])
        {
            memset(trie[tot],0,sizeof(trie[tot]));
            trie[p][ch]=(tot++);
        }
        p=trie[p][ch];
        End[p]++;
    }
}
bool check(char *s)//这个其实就是Search函数,只不过我们改名了.
{
    int len=strlen(s),p=0;
    fir(i,0,len-1)//找出所有的前缀
    {
        int ch=s[i]-'0';
        p=trie[p][ch];
        if(End[p]==1)//如果出现过了
            return false;
    }
    return true;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        fir(i,1,n)
        {
            scanf("%s",st[i]);
            insert(st[i]);
        }
        int ok = 1;
        fir(i,1,n)
            if(check(st[i]))//判断
            {
                ok = 0;
                break;
            }
        if(ok) 
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}