传说中的字典树
#include <stdio.h>
#include <string.h>
#include "stdlib.h"

char in[35];

typedef struct
{
    int next[53];
    int count;
}node;
node trie[150005];
int now;

char st[10005][35];
int snow;

void init()
{
    
    memset(&trie[0],0,sizeof(trie));
    now = 1;
    snow = -1;
}

int cmp(const void *a, const void *b)
{

    return strcmp((char *)a, (char *)b);
}

int insert(char *str, int len)
{
    int i;
    int p = 0; 
    int hash;
    for (i=0; i<len; i++)
    {
        hash = str[i]-20;
        if (!trie[p].next[hash])
        {
            memset(&trie[now], 0, sizeof(node));
            trie[p].next[hash] = now++;
        }
        p = trie[p].next[hash];
    }
    trie[p].count++;
    return p;
}

int search(char *str, int len)
{
    int i;
    int p = 0; 
    int hash;
    for (i=0; i<len; i++)
    {
        hash = str[i]-20;
        if (!trie[p].next[hash])
        {
            return 0;
        }
        p = trie[p].next[hash];
    }
    if(!trie[p].count)
    {
        return 0;
    }
    return p;
}

int main()
{

    int p, i;
    int count = 0;
    int len;
    init();
    while (gets(in))
    {
        len = strlen(in);
        p = search(in, len);
        if (!p)
        {
            insert(in, len);
            strcpy(st[++snow], in);
        }
        else
        {
            trie[p].count ++;
        }
        count ++;
    }

    qsort(st, snow+1, sizeof(st[0]), cmp);
    for (i=0; i<snow+1; i++)
    {
        printf("%s", &st[i]);
        len = strlen(st[i]);
        printf(" %.4lf\n", (double)trie[search(st[i], len)].count/(double)count*100);
    }
    return 0;
}