字典樹的一個應用，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=2001
#include <stdio.h>
#include <string.h>

struct
{
    int next[26];
    int c[26];
    int flag;
}trie[35000];
int now;

void initt ()
{

    now = 0;
    for ( int i=0; i<26; i++ )
    {
        trie[now].next[i] = 0;
        trie[now].c[i] = 0;
    }
    trie[now].flag = 0;
    now ++;
}

int add ()
{

    for ( int i=0; i<26; i++ )
    {
        trie[now].next[i] = 0;
        trie[now].c[i] = 0;
    }
    trie[now].flag = 0;
    now ++;

    return now - 1;
}

int ser ( char *str )
{

    int pre = 0;
    while ( *str != 0 )
    {
        int addr = *str - 'a';
        if ( ! trie[pre].next[addr] )
        {
            return 0;
        }
        pre = trie[pre].next[addr];
        str ++;
    }
    if ( ! trie[pre].flag )
    {
        return 0;
    }
    return pre;
}
 
int ins ( char *str )
{

    int pre = 0;
    while ( *str != 0 )
    {
        int addr = *str - 'a';
        if ( ! trie[pre].next[addr] )
        {
            trie[pre].next[addr] = add ();
        }
        trie[pre].c[addr] ++;
        pre = trie[pre].next[addr];
        str ++;
    }
    trie[pre].flag = 1;

    return pre;
}

void check ( char *str )
{

    char *s = str;
    int pre = 0;
    while ( *str != 0 )
    {
        int addr = *str - 'a';
        if ( trie[pre].c[addr] == 1 )
        {
            while ( s <= str )
            {
                printf ( "%c", *s );
                s ++;
            }
            printf ( "\n" );
            return;
        }
        pre = trie[pre].next[addr];
        str ++;
    }
    printf ( "%s\n", s );
}

char str[1005][25];

int main ()
{

    char in[25];

    int n = 0;
    initt ();
    while ( scanf ( "%s", in ) != EOF )
    {
        int len = strlen ( in );
        if ( len )
        {
            strcpy ( str[n++], in );
            if ( ! ser ( in ) )
            {
                ins ( in );
            }
        }
    }
    for ( int i=0; i<n; i++ )
    {
        printf ( "%s ", str[i] );
        check ( str[i] );
    }
    return 0;
}