Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
#include "cstring" 
#include "cctype" 
#include "algorithm" 
using namespace std;

const int MAX = 350000;
const int BUFLEN = 200;
char buf[ BUFLEN ];   
int T;   

char text[ 80 ][ 80 ];
int len[ 80 ], tSize;
int frequency[ 26 ];
int cmpList[ 26 ], aSize;
bool cmp( const int &i, const int &j )
{
 return frequency[ i ] > frequency[ j ];
}

char answer[ 30 ];
int map[ 26 ];
int cur[ 26 ];
bool visited[ 26 ];
int ansCount;

class Trie
{
public:
 Trie()
 { 
  for ( count = 1; count < 21; count ++ )
   root[ count ] = count;
  memset( lenMark, false, sizeof( lenMark ) );
  memset( child, 0, sizeof( child ) );
  memset( isLeaf, false, sizeof( isLeaf ) );
 }
 void insert( char *word )
 {
  int length = strlen( word );
  lenMark[ length ] = true;
  int next = root[ length ], i;
  for ( i = 0; i < length; i ++ )
  {
   int pos = word[ i ] - 'A';
   if ( child[ next ][ pos ] == 0 )
    child[ next ][ pos ] = count ++;
   
   next = child[ next ][ pos ];
  }
  isLeaf[ next ] = true;
 }
 bool find( int t )
 {
  return find( t, 0, root[ len[ t ] ] );
 }
 bool find( int t, int index, int ptr )
 {
  if ( !ptr )
   return false;
  if ( index == len[ t ] )
   return isLeaf[ ptr ];
  
  int code = map[ text[ t ][ index ] ];
  if ( code >= 0 )
   return find( t, index + 1, child[ ptr ][ code ] );
  else
  {
   for ( int i = 0; i < 26; i ++ )
    if ( !visited[ i ] )
    {
     visited[ i ] = true;
     map[ text[ t ][ index ] ] = i;
     if ( find( t, index + 1, child[ ptr ][ i ] ) )
     {
      visited[ i ] = false;
      map[ text[ t ][ index ] ] = -1;
      return true;
     }
     map[ text[ t ][ index ] ] = -1;
     visited[ i ] = false;
    }
  }
  
  return false;
 }
 bool hasLength( int length ) { return lenMark[ length ]; }
private:
 int child[ MAX ][ 26 ];
 bool isLeaf[ MAX ];
 int root[ 21 ];
 bool lenMark[ 21 ];
 int count;
}dicList;

void readDic()
{
 int N;
 scanf( "%d", &N );
 while ( N -- )
 {
  scanf( "%s", buf );
  dicList.insert( buf );
 }
}

bool readText()
{
 bool mark = true;
 tSize = 0;
 memset( frequency, 0, sizeof( frequency ) );
 int i, j;
 
 scanf( "\n" );
 while ( gets( buf ) )
 {
  if ( buf[ 0 ] == '\0' ) break;
  for ( i = 0; buf[ i ] != '\0'; i ++ )
   if ( isalpha( buf[ i ] ) )
   {
    for ( j = 0; buf[ i ] != '\0' && isalpha( buf[ i ] ); i ++, j ++ )
    {
     text[ tSize ][ j ] = buf[ i ] - 'A';
     frequency[ buf[ i ] - 'A' ] ++;
    }     
    len[ tSize ++ ] = j;
    
    if ( j > 20 || !dicList.hasLength( j ) )
     mark = false;
    
    i --;
   }
 }
 
 return mark;
}

void dealText()
{
 int i;
 aSize = 0;
 for ( i = 0; i < 26; i ++ )
  if ( frequency[ i ] > 0 )
   cmpList[ aSize ++ ] = i;
 
 sort( cmpList, cmpList + aSize, cmp );
 
 ansCount = 0;
 memset( map, 0xff, sizeof( map ) );
 memset( cur, 0xff, sizeof( cur ) );
 memset( visited, false, sizeof( visited ) );
}

bool check()
{
 for ( int i = 0; i < tSize; i ++ )
  if ( !dicList.find( i ) )
   return false;
 return true;
}

void dfs( int depth )
{
 int i;
 if ( depth == aSize )
 {
  ansCount ++;
  for ( i = 0; i < 26; i ++ )
   answer[ i ] = '*';
  for ( i = 0; i < 26; i ++ )
   if ( map[ i ] != -1 )
    answer[ map[ i ] ] = char( i + 'A' );
  answer[ i ] = '\0';
  return;
 }
 
 for ( i = 0; i < 26; i ++ )
  if ( !visited[ i ] )
  {
   visited[ i ] = true;
   map[ cmpList[ depth ] ] = i;
   if ( check() )
   {
    dfs( depth + 1 );
    if ( ansCount == 2 )
     return;
   }
   visited[ i ] = false;
  }
 map[ cmpList[ depth ] ] = -1;
}

int main()
{
 readDic();
 scanf( "%d", &T );
 scanf( "\n" );
 
 while ( T -- )
 {
  if ( !readText() )
  {
   puts( "#No solution#" );
   continue;
  }
  dealText();
  
  dfs( 0 );
  if ( ansCount == 0 )
   puts( "#No solution#" );
  else if ( ansCount == 1 )
   puts( answer );
  else
   puts( "#More than one solution#" );
 }
 
 return 0;
}