Poj Solution 1072

http://poj.org/problem?id=1072

#include <stdio.h>
#include <string.h>
#include <algorithm>


//#define DEBUG
//#define PRINT_TREE 


#ifdef DEBUG
#include <time.h>
#endif

using namespace std;

const char NONE = 30;
const char WORD = 50;

struct node
{
    node(){ p=0; m=''; for(int i=0;i<27;i++)id[i]=NONE; }
        
    char id[27];
    int *p;
    char m;
}mem[150000];

node a_word,root;
int use_node=0;

int new_node()
{
    return use_node++;
}

void insert( node *pnd, char c )
{

    int *q = new int[ pnd->m + 1];
    
    copy( pnd->p, (pnd->p)+(pnd->m), q );
        
    q[pnd->m] = new_node();
        
    pnd->id[c-'A'] = pnd->m;
    pnd->m++;

    delete pnd->p;
    pnd->p = q;

    return ;
}

inline void set_word( node *pnd )
{
    pnd->id[27] = WORD;
}

inline node *get_child( node *pnd,char c)
{
    int s;
    if( (s=pnd->id[c-'A']) == NONE )return 0;
    else return &mem[ pnd->p[s] ];
}

inline bool is_word( node *pnd)
{
    return pnd->id[27] == WORD;
}

void creat(node *p,char *word)
{
    if( *word == '')
    {
        set_word( p );
    }
    else
    {
        node *q=get_child(p,*word);
    
        if( !q )
        {
            insert(p,*word);
            q=get_child(p,*word);
        }
    
        creat( q,word+1 );
    }
}

char *word[2000];
int n;


bool cmp( char *a, char *b )
{
    return *a > *b || ( *a == *b ) && strcmp(a,b) < 0;
}


char s[100];

void print( node *p, int k )
{
    if( !p ) return;
    
    if( is_word(p) )
    {
        s[k] ='';
        printf(":%sn",s);
    }
    
    char a;
    for( a='A'; a<='Z'; a++ )
    {
        s[k]=a;
        print(get_child( p, a ), k+1 );
    }
}

char table[26];
char ans[26];
bool used[26];
int answer;



void init()
{
    char w[100], l, c;

    n=0;

    while( ( c = getchar() )=='n' )
        ;
    ungetc( c, stdin );

    while(1)
    {
        if(scanf( "%s", w )!=1)break;
        
        if( w[0] == '' ) break;
        
        l = strlen( w );

        word[n] = new char[l+2];
        word[n][0] = l;
        strcpy( word[n]+1, w );
         
        n++;
        while( ( c = getchar() )==' ' )
            ;
        if( c=='n')
        {
            c=getchar();
            if(c=='n')break;
            else ungetc(c,stdin);
        }
        else
        {
            ungetc(c,stdin);
        }
        if(n>1500)
        {
            n=n;
        }
    }
    
    sort(word, word+n, cmp);
    n=std::unique_copy(word, word+n,word )-word;

    int i;
    for( i=0;i<26;i++)
    {
        table[i]='*';
        used[i] = false;
    }
    answer=0;

#ifdef DEBUG
    printf("%d wordsn",n);
#endif
}

char *d_word[50010];




void creat_dictionary()
{
    int i ,l, m;
    char w[100];
    scanf( "%d", &m );

    for( i=0; i<m; i++ )
    {
        scanf( "%s", w );
    
        l = strlen( w );
        d_word[i] = new    char[l+2];
        
        d_word[i][0] = l;
        strcpy( d_word[i]+1, w );

        creat( &root, w );
    }

}

inline int certain(char *s)
{
    int i,j;
    for(i=1,j=0; s[i]; i++)
        if(table[s[i]-'A']!='*')
            j++;
    return j;
}

int cmp2(char *a,char *b)
{
    return certain(a)>certain(b);
}


bool find( int wn, int cn, node *p )
{

    if( wn>=n ) 
    {
        answer++;
        copy(table,table+26,ans);

        return answer>1;
    }
    
    if( !p )return false;

    if( cn == word[wn][0] )
    {
        if( is_word(p) )
        {
            sort( word+wn+1,word+n,cmp2 );

            if( find( wn+1, 0, &root ) ) return true;
        }
    }
    else
    {
        char c = word[wn][cn+1], d;
        
        if( table[c-'A'] == '*' )
        {
            for( d='A'; d<='Z'; d++ )
            if(!used[d-'A'])
            {
                table[c-'A'] = d;
                
                used[d-'A'] = true;
                if( find( wn, cn+1, get_child(p,d) ) ) return true;
                used[d-'A'] = false;
            }
            table[c-'A'] = '*';
        }
        else    if( find( wn, cn+1, get_child(p, table[c-'A']) ) ) return true;
    }

    return false;
}        

int main()
{
    int cas;
#ifdef DEBUG
    freopen("E.in","r",stdin);
    long t=clock();
#endif

    creat_dictionary();


#ifdef PRINT_TREE    
    print(&root,0);
#endif

#ifdef DEBUG
    printf( "%dmsn", clock()-t );
#endif
    
    scanf("%d",&cas);
    
    while( cas-- )
    {
        init();
        if( find( 0, 0, &root ) )
            printf( "#More than one solution#n" );
        else
        {
            if( answer == 0 )
                printf( "#No solution#n" );
            else 
            {
                char out[26];
                int i;

                for( i=0; i<26; i++ )
                    out[i]='*';
                
                for(i=0; i<26; i++ )
                if(ans[i-'A']!='*')
                {
                    out[ans[i]-'A']=i+'A';
                }

                for( i=0; i<26; i++ )
                    printf( "%c", out[i] );
                printf( "n" );
            }
        }
    }

    return 0;
}