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;   

}