【Trie】Phone List

【题目链接】：

【题意】

问是否存在一组公共前缀。如果存在输出“NO”，否则输出“YES”

【题解】

首先建出Trie树来，然后开始记录所有的字符串，然后进行再跑一遍。看看是否在跑的过程中遇到某个位置上标记。

裸的模板题。

【代码】

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N = 2e4 +;

 int son[N*][];

 bool cnt[N*],f;

 int T,n,idx;

 char str[N][];

 void Insert(char s[]){

     //printf("###%s\n",s);

     int p =  ;

     for(int i= ; s[i] ; i++ ){

         int t = s[i] - '';

         if( !son[p][t] ) son[p][t] = ++idx ;

         p = son[p][t];

     }

     cnt[p] = true;

 }

 void Query(char s[]){

     //printf("$$$%s\n",s);

     int p =  ;

     for(int i= ; s[i+] ; i++ ){

         int t = s[i] - '';

         if( !son[p][t] ) break;

         p = son[p][t];

         if( cnt[p] ) f = true;

     }

 }

 void Init(){

     f = false ;

     idx =  ;

     memset(cnt,false,sizeof cnt );

     memset(son,,sizeof son );

 }

 int main()

 {

     scanf("%d",&T);

     while(T--){

         Init();

         scanf("%d",&n);

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

             scanf("%s",str[i]);

             Insert(str[i]);

         }

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

             Query(str[i]);

         }

         puts(f?"NO":"YES");

     }

     return ;

 }

 /*

 40

 2

 9999999999

 999999999

 2

 9999999999

 999999998

 2

 012

 12

 2

 012

 1

 2

 0

 01

 2

 012

 1

 */