poj 3630 Phone List

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define N 100005

 using namespace std;

 int Trie[N][];

 int nodeN;

 int main()

 {

 int t, n, i, j, isPrefix, flag;

 char ph[];

 scanf("%d", &t);

 while(t--)

 {

 scanf("%d", &n);

 isPrefix=;

 nodeN=;

 memset(Trie[], , sizeof(int)*);

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

 {

   scanf("%s", ph);

   flag=;

   int cur=;

   if(!isPrefix)

   for(j=; ph[j]; ++j)

   {

     int k=ph[j]-'';

     if(!Trie[cur][k])

     {

       if(i!= && !flag)//利用第一个字符串建立一个初始的trie树

       {

           flag=;//建立了新节点（如果当前 cur 节点还有孩子说明没有公共前缀， 否则说明当前路已经走到了尽头，产生了公共前缀）

           int c;

         　for(c=; c<; ++c)//检查时候当前节点cur是否有孩子节点

 　　　　　   if(Trie[cur][c])

 　　　　　　　　 break;

 　　　　　　if(c>=)

38　　　　　　 {

    　　　　　　 isPrefix=; //没有孩子节点，则说明产生了公共前缀

 　　　　　　　　break;

   　　　　　}

 　　　  }

        Trie[cur][k]=++nodeN;

        memset(Trie[nodeN], , sizeof(int)*);

      }
      cur=Trie[cur][k];

    }

   if(flag== && i!=)//如果不是第一个字符串，而且在遍历整个树的时候没有发现建立新的节点，则说明当前字符串必然是之前某个字符串的公共前缀

     isPrefix=;

  }

   if(isPrefix)

     printf("NO\n");

   else printf("YES\n");

 }

 return ;

 }

 /*
  好不容易想用一下链表来写一下，还超时啊。。。。
*/
 1 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 class Trie

 {

  public:

    Trie *ch[];

    Trie()

    {

       memset(ch, , sizeof(ch));

    }

 };

 int main()

 {

    int t, n, i, j, isPrefix, flag;

    char ph[];

    scanf("%d", &t);

    while(t--)

    {

       scanf("%d", &n);

       Trie *root=new Trie();

       isPrefix=;

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

       {

            scanf("%s",  ph);

            flag=;

            Trie * cur=root;

            if(!isPrefix)

             for(j=; ph[j]; ++j)

             {

               int k=ph[j]-'';

               if(!cur->ch[k])

               {

                   if(i!= && !flag)

                   {

                      flag=;

                      int c;

                      for(c=; c<; ++c)

                        if(cur->ch[c])

                          break;

                      if(c>=)

            {

               isPrefix=;

               break;

                }

                   }

                  cur->ch[k]=new Trie();

         }

         cur=cur->ch[k];

       }

      if(flag== && i!=)

         isPrefix=;

       }

       if(isPrefix)

          printf("NO\n");

       else printf("YES\n");

    }

    return ;

 }

巴特西

poj 3630 Phone List

最新文章

热门文章