学步园

/*

原来动态构树是这么费时间的。。。20000个单词最长为20个的题，跑到了1688MS，

题目：
题目大概是说找出相同的字符串并且统计个数。

分析：
因为昨天刚学完trie树，现在练了几道，有点感觉了，其实本题应该是可以用快排直接安字典序进行排序，然后按前后关系来进行判断有多少个的，下面继续讲讲trie树动态构树法吧：看程序解析

*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define X 20005
int d[X],cnt,print[X];
structtrie
{
    int id;
    trie *p[4];
    trie()
    {
        id = -1;
        memset(p,NULL,sizeof(p));
    }
}root;
int insert(trie *r,char *s)
{
    int c;
    for(int i=0;s[i];i++)
    {
        if(s[i]=='A')
            c = 0;
        else if(s[i]=='G')
            c = 1;
        else if(s[i]=='T')
            c = 2;
        else
            c = 3;
        if(r->p[c]==NULL)
            r->p[c] = new trie();
        r = r->p[c];
    }
    if(r->id==-1)
        r->id = cnt++;
    return r->id;
}
int main()
{
    int m,n,q;
    char ch[25];
    while(scanf("%d%d",&m,&n),m||n)
    {
        memset(d,0,sizeof(d));
        cnt = 0;
        trie *r = &root;
        for(int i=0;i<m;i++)
        {
            scanf("%s",ch);
            //cout<<"测试"<<endl;
            q = insert(r,ch);
            d[q]++;
        }
        memset(print,0,sizeof(print));
        for(int i=0;i<cnt;i++)
            print[d[i]]++;
        for(int i=1;i<=m;i++)
            printf("%d\n",print[i]);
    }
    return 0;
}