「题解」Phone List

题目链接:POJ 3630/LibreOJ 10049

题目

题目描述

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

数据范围

$$1\leq T\leq 40,1\leq n\leq 10^4$$

题解

思路

$\texttt{Trie}$ 裸题。

代码

#include<cstdio>
#include<cstring>
#define reg register
const int MAXN=10000+5;
const int MAXSIZE=10+5;
struct Trie{
    int cnt;
    bool vis[MAXN*MAXSIZE];
    int ch[MAXN*MAXSIZE][MAXSIZE];
    inline void Clear(void){
        cnt=1;
        memset(vis,false,sizeof(vis));
        memset(ch,0,sizeof(ch));
        return;
    }
    inline bool insert(reg char str[]){
        reg bool flag=false;
        reg int i,ID=1,len=strlen(str);
        for(i=0;i<len;++i){
            int c=str[i]-'0';
            if(!ch[ID][c])
                ch[ID][c]=++cnt;
            else if(i==len-1)
                flag=true;
            ID=ch[ID][c];
            if(vis[ID])
                flag=true;
        }
        vis[ID]=true;
        return flag;
    }
};
char str[16];
int T,n;
Trie Tr;
int main(void){
    reg bool ans;
    scanf("%d",&T);
    while(T--){
        ans=false;
        Tr.Clear();
        scanf("%d",&n);
        while(n--){
            scanf("%s",str);
            if(Tr.insert(str))
                ans=true;
        }
        puts(!ans?"YES":"NO");
    }
    return 0;
}