hdu1671

个人感觉trie作为一种数据结构其实并不难，在hdu上早先干掉了1251、1075，今天干掉了1247、1671，1247看懂题以后想了一下没有想出，后来参照网上代码，输入数据存入字典树后，再重新例举已输入的串，每一个串代入到字典树中，先判断是不是前缀，然后判断其后的那个单词是不是在字典树中，1671个人认为较为简单，设置一个count成员变量记录有多少个串通过该字母，判断的时候只要count>1&&x[i+1]=='/0'就可以了。

    附1671代码：

    #include<iostream>

using namespace std;

const int tot=11;

const int fir='0';

const int len=10000;

struct Node

{

       int son[tot];

       int end;

       int count;

       void to0()

       {

            count=0;

            memset(son,-1,sizeof(son));

            end=0;    

       }           

}node[len*10];

int num;

void insert(char *x)

{

     int len = strlen(x),root = 0;

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

         int k = x[i]-fir;

         if (node[root].son[k]==-1){

            num ++;

            node[root].son[k] = num;

            node[num].to0();                  

         }

         root=node[root].son[k];

         node[root].count++;   

     }

     node[root].end++;   

}

int search(char *x)

{

     int len=strlen(x),root=0,i;

     for ( i = 0; i<len; i++){

         int temp=x[i]-fir;

         if (node[root].son[temp]==-1)return 0;

         root=node[root].son[temp];

         if (node[root].count>1&&x[i+1]=='/0')return 1;//此句让我wa了N次 

     }

     return 0;

}

char x[10001][11];

int main()

{

    int  t;

    cin >> t;

    while (t--){

          int n;

          cin >> n;

          num=0;

          node[0].to0();

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

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

              insert(x[i]);     

          }    

          int check = 0;

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

              if (search(x[i])){check = 1;break;}

          }

          if (check){printf("NO/n");}

          else printf("YES/n");

    }

    //system("pause");

    return 0;   

}