1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 #define maxnode 400010 6 #define sigma_size 22 7  8 char a[maxnode][sigma_size]; 9 int t[maxnode];10 int n,m;11 //struct Trie12 //{13     int ch[maxnode][sigma_size];        //ch[i][j]：记录结点i的那个编号为j的子节点14     int val[maxnode];                    //val[i]：i节点的附加信息，15                                          //若val[i]=0不是还没到单词结束。否则val[i]为该单词的出现次数16     int sz;17     void Trie()18     {19         sz=1;20         memset(ch,0,sizeof(ch));21         memset(val,0,sizeof(val));22         memset(t,0,sizeof(t));23     }24     int idx(char c)                       //idx(c)即字符c的编号。25     {26         //A G C T27         if (c==‘A‘)     return 1;28         if (c==‘G‘)     return 2;29         if (c==‘C‘)     return 3;30         if (c==‘T‘)     return 4;31         //return c-‘A‘;                    //第一个字符是A32     }33     void Insert(char s[sigma_size],int v)34     {35         int u=0,n=strlen(s);36         for (int i=0;i<n;i++)37         {38             int c=idx(s[i]);39             if (!ch[u][c])40             {41                 memset(ch[sz],0,sizeof(ch[sz]));42                 val[sz]=0;43                 ch[u][c]=sz++;44             }45             u=ch[u][c];46         }47         //val[u]=v;48         val[u]+=v;49     }50     int Query(char s[sigma_size])     //times of s51     {52         int u=0,c;53         int tm=strlen(s);54         for (int i=0;i<tm;i++)55         {56             //c=s[i]-‘A‘;57             c=idx(s[i]);58             if (!ch[u][c])    return 0;59             u=ch[u][c];60             //if (val[u]==1)  return true;    //若此时s还没走完但trie树上已经走到结尾了，即树上单词是s的前缀61         }62         return val[u];63     }64 //};65 66 int main()67 {68     //freopen("in.txt","r",stdin);69     //ios::sync_with_stdio(false);70 71     //while (cin>>n>>m)72     while(~scanf("%d%d",&n,&m))73     {74         Trie();75         if ((n!=0)&&(m!=0))76         {77             for (int i=1;i<=n;i++)78             {79                 //cin>>a[i];80                 scanf("%s",a[i]);81                 Insert(a[i],1);82             }83             for (int i=1;i<=n;i++)84             {85                 int tm=Query(a[i]);86                 t[tm]++;87             }88             for (int i=1;i<=n;i++)89                 printf("%d\n",t[i]/i);90             //cout<<endl;91         }92         else break;93     }94 95     return 0;96 }