# 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];

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;
}

#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 )
{
copy(table,table+26,ans);

}

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
{
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;
}

```
This entry was posted in poj. Bookmark the permalink.