給出一個昵稱列表，統(tǒng)計每個昵稱出現(xiàn)的次數(shù)（昵稱中只可能出現(xiàn)大小寫字母，一律按小寫字母處理）。其中昵稱個數(shù)N<=100000，每個昵稱長度L<=100，不同昵稱的總數(shù)T不超過5000。

有以下幾種思路：

（1）排序，字符串交換的時候只交換指針而不交換字符串本身，這樣做理論上是可以接收的，沒有嘗試；

（2）字典樹，直接在結(jié)點中記錄出現(xiàn)的次數(shù)，最后遍歷樹即可，我是這么做的，全部數(shù)據(jù)用了3.92s；

（3）Hash Table，hash 函數(shù)的設(shè)計是把字符串當(dāng)成26進(jìn)制整數(shù)，迭代求出hash函數(shù)值，求hash函數(shù)值的時間復(fù)雜度為O(L)，總時間復(fù)雜度O(Ln)。

以下是我的代碼，是用字典樹實現(xiàn)的：

#include<stdio.h>
typedef struct NODE
{
    struct NODE *son[26];
    long count;
}Nick;
long test,n;
Nick *root;
Nick* newnode()
{
    long i;
    Nick *p;
    p=(Nick*)malloc(sizeof(Nick));
    p->count=0;
    for(i=0;i<26;i++)
      p->son[i]=NULL;
    return p;
}
void ins(char *s,Nick *p)
{
    long t;
    t=*s-'a';
    if(p->son[t]!=NULL)
      p=p->son[t];
    else
    {
       p->son[t]=newnode();
       p=p->son[t];
    }
    if(s[1]==0)
      p->count++;
    else
     ins(s+1,p);
}
void release(Nick *node)
{
    long i;
    if(node!=NULL)
    {
       for(i=0;i<26;i++)
         release(node->son[i]);
       free(node);
    }
}
void travel(Nick *p,char *s,long dep)
{
    long i,j;
    if(p->count>0)
    {
       for(j=0;j<dep;j++)
         printf("%c",s[j]);
       printf(" %ld\n",p->count);
    }
    for(i=0;i<26;i++)
      if(p->son[i]!=NULL)
      {
         s[dep]=i+'a';
         travel(p->son[i],s,dep+1);
         s[dep]=0;
      }
}
void init()
{
    long i,j,k;
    char s[150]={0},out[150]={0};
    scanf("%ld",&test);
    for(i=1;i<=test;i++)
    {
       root=newnode();
       scanf("%ld",&n);
       for(j=1;j<=n;j++)
       {
          scanf("%s",s);
          for(k=0;s[k]!=0;k++)
            if(s[k]>='A'&&s[k]<='Z')
              s[k]+='a'-'A';
          ins(s,root);// Insert
       }
       travel(root,out,0);
       release(root);// Release
       printf("\n");
    }
}
int main()
{
    freopen("nickname.in","r",stdin);
    freopen("nickname.out","w",stdout);
    init();
return 0;
}