Phone list（Trie树模板）

时间：2021-10-12 23:22:08

Phone List

共t组数据，给定n个长度不超过10的字符串，问其中是否存在两个数S,T，使得S是T的前缀。

存在则输出NO，不存在输出YES

输入样例#1： 
2

3

911

97625999

91125426

5

113

12340

123440

12345

98346
输出样例#1： 
NO

YES
此题转自洛谷UVA11362

Trie树模板题，可以一边构建Trie树一边判断答案，详见代码。
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read()

{

    int f=,x=;

    char ch=getchar();

    while(ch<'' || ch>'') {if(ch=='-') f=-; ch=getchar();}

    while(ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int T,n,cnt=;

bool flag;

int ove[],pre[],tree[][];

char a[];

/*

tree是trie树

ove[i]表示以i为结点的数

pre[i]表示i结点的出边数

*/

void insert(char *s)//插入+查找

{

    int len=strlen(s),p=;

    for(int i=;i<len;i++)

    {

        int c=s[i]-'';//若是字母串，变为-'a'

        if(tree[p][c]==)//若当前结点p的子节点中没有要找的c，则将c插入

            tree[p][c]=++cnt;

        p=tree[p][c];//继续查找

        pre[p]++;

        if(ove[p])//某串是该串的前缀

        {

            flag=;

            break;

        }

    }

    ove[p]=;//标记该串在结点p结束

    if(pre[p]>)//该串是某串的前缀

        flag=;

}

int main()

{

    T=read();

    int i,j;

    while(T--)

    {

        memset(tree,,sizeof(tree));

        memset(ove,,sizeof(ove));

        memset(pre,,sizeof(pre));

        flag=;

        cnt=;

        n=read();

        for(i=;i<=n;i++)

        {

            scanf("%s",a);

            if(!flag)

                insert(a);

        }

        if(flag)

            printf("NO\n");

        else

            printf("YES\n");

    }

    return ;

}

这是代码

 

相关文章