Phone List POJ - 3630(trie)

题意：传送门
题解：判断一堆字符中有没有谁是谁的前缀，直接使用$trie$trie，对于每个字符串结束加个标记即可。
$code:$code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
int T,n,son[N][10],idx;
bool f[N];
char str[20];
bool insert()
{
    int p=0;
    bool has_new=false;
    bool has_found=false;
    for(int i=0;str[i];i++){
        int u=str[i]-'0';
        if(!son[p][u]){
            son[p][u]=++idx;
            has_new=true;
        }
        p=son[p][u];
        if(f[p])has_found=true;
    }
    f[p]=true;
    return has_new&&!has_found;
}
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(son,0,sizeof(son));
        memset(f,false,sizeof(f));
        idx=0;
        bool res=true;
        for(int i=0;i<n;i++){
            scanf("%s",str);
            if(!insert())res=false;
        }
        if(res)puts("YES");
        else puts("NO");
    }
    return 0;
}