http://acm.pku.edu.cn/JudgeOnline/problem?id=1072
Код:
#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; }