学步园

昵称（nickname.pas/cpp  时限:2S）

【题目描述】

使用过腾讯QQ的人都知道，每个QQ号是唯一的，但是有可能多个QQ号对应的昵称是相同的。现在假设你是一个腾讯的一个部门经理，上级领导给你一个昵称列表，要求你统计出每个昵称出现的次数。

【数据输入】

第一行是一个整数T，表示有T组测试输入数据。

每组数据格式如下：

第一行是一个整数N（1≤N≤100,000），表示昵称的个数；

接下来N行，每行是一个昵称字符串，每个昵称不超过100个字符；

不同的昵称总数不超过5000，昵称中不区分大小写，即A等效于a。

    在两组测试输入数据之间有一个空行隔开！

【数据输出】

对应每组测试输入数据，每行输出一个昵称及出现次数，昵称和次数之间用一个空格隔开，昵称用字典顺序输出，并且全部是小写字母。

    不同组的输出数据，没有空行隔开。

【输入样例】

1

4

carp

inkfish

peipei

carp

【输出样例】

carp 2

inkfish 1

peipei 1

评测数据下载：http://pan.baidu.com/share/link?shareid=432744&uk=255096381&third=15

解法：trie（字典树）。

用字典树来记录昵称，然后就是裸题了，在这里子讲一下我的建树方法。

用 f[i][j] 记录以 i 号节点为父亲，其子节点中是否存在 j （j=0..25，分别代表‘a’...‘z’），初始为0，若 f[i][j] 的值大于0，则以 i 号节点为父亲，其子节点中存在 j ，并且以 i 号节点为父亲，子节点为 j 的节点的编号为 f[i][j]。

用 v[i] 记录从根0到 i 号节点的这条路径上所代表的字符串出现几次，初始为0，若 v[i] !=0，则从根0到 i 号节点的这条路径上的字符组成的字符串是存在的。

代码：

#include<cstdio>
#include<cstring>
#define maxn (5000*100+100)
using namespace std;

int num,len,f[maxn][26],v[maxn]; 
char s[100+10];

void init()
{
  freopen("nickname.in","r",stdin);
  freopen("nickname.out","w",stdout);
}

void insert(int i,int j)//插入字符串 
{
  int k=s[j]-'a';
  if(f[i][k]==0)
    {
      f[i][k]=(++num),v[num]=0;
      memset(&f[num][0],0,sizeof(int)*26);
    }  
  if(j+1<len)insert(f[i][k],j+1);
  else v[f[i][k]]++;
}

void write(int i)//输出答案 
{
  int j,k;
  if(v[i]!=0)
    {
      for(j=0;j<num;j++)
        printf("%c",s[j]);
      printf(" %d\n",v[i]);  
    }
  for(k=0;k<26;k++)
    if(f[i][k]!=0)
      {
        s[num++]='a'+k;
        write(f[i][k]);
        num--;
      }    
}

void chuli()//处理大小写 
{
  int i;
  for(i=0;i<len;i++)
    if(s[i]<'a')s[i]='a'+s[i]-'A';
}

void work()
{
  int n,i,j,k;   num=v[0]=0;
  memset(&f[0][0],0,sizeof(int)*26);
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    {
      scanf("%s",s),len=strlen(s);
      chuli(),insert(0,0);
    }  
  num=0;  
  write(0);  
}

int main()
{
  init();

  int t,i;
  scanf("%d",&t);
  for(i=1;i<=t;i++)work();

  return 0;
}