題目鏈接:http://poj.org/problem?id=1035
思路分析:
1、使用哈希表存儲字典
2、對待查找的word在字典中查找,查找成功輸出查找成功信息
3、若查找不成功,對word增、刪、改處理,然后在字典中查詢,若查找成功則記錄處理后單詞在字典中的次序
4、對次序排序再輸出
注:對word處理后可能會出現重復,需要進行判斷重
?
代碼如下:
#include <iostream> using namespace std;const int N = 50; const int tSize = 12007; char hashDic[tSize][N]; int stateDic[tSize]; int rankDic[tSize];char words[tSize][N]; int stateW[tSize];int Ans[tSize]; int ansLen;int InsertDic( char *key, int pos ) {int len = strlen( key );unsigned int hashVal = 0;for ( int i = 0; i < len; ++i )hashVal = ( hashVal * 26 + key[i] - 'a' ) % tSize;while ( stateDic[hashVal] != 0 &&strcmp( hashDic[hashVal], key ) != 0 ){hashVal = ( hashVal + 1 ) % tSize;}if ( stateDic[hashVal] == 0 ){stateDic[hashVal] = 1;strcpy( hashDic[hashVal], key );rankDic[hashVal] = pos;return true;}return false; }int InsertWords( char *key ) {int len = strlen( key );unsigned int hashVal = 0;for ( int i = 0; i < len; ++i )hashVal = ( hashVal * 26 + key[i] - 'a' ) % tSize;while ( stateW[hashVal] != 0&& strcmp( words[hashVal], key ) != 0 ){hashVal = ( hashVal + 1 ) % tSize;}if ( stateW[hashVal] == 0 ){stateW[hashVal] = 1;strcpy( words[hashVal], key );return true;}return false; }int Find( char *key ) {int len = strlen( key );unsigned int hashVal = 0;for ( int i = 0; i < len; ++i )hashVal = ( hashVal * 26 + key[i] - 'a' ) % tSize;while ( stateDic[hashVal] != 0 &&strcmp( hashDic[hashVal], key ) != 0 ){hashVal = ( hashVal + 1 ) % tSize;}if ( stateDic[hashVal] == 0 )return -1;elsereturn hashVal; }int cmp( const void *a, const void *b ) {int *pA = (int *)a;int *pB = (int *)b;return rankDic[*pA] - rankDic[*pB]; }int main( ) {int countDic = 0;char word[N];memset( stateDic, 0, sizeof( stateDic ) );while ( scanf( "%s", word ) == 1 ){if ( word[0] == '#' )break;InsertDic( word, countDic++ );}while ( scanf( "%s", word ) == 1 ){char copy[N];int indexWord;int len = strlen( word );if ( word[0] == '#' )break;ansLen = 0;memset( stateW, 0, sizeof( stateW ) );printf( "%s", word );indexWord = Find( word );if ( indexWord > -1 ){printf( " is correct\n" );continue;}for ( int i = 0; i <= len; ++i ){int j;strcpy( copy, word );for ( j = len; j >= i; --j )copy[j + 1] = copy[j];for ( char a = 'a'; a <= 'z'; ++a ){copy[i] = a;indexWord = Find( copy );if ( indexWord > -1 && InsertWords( copy ) )Ans[ansLen++] = indexWord;}}for ( int i = 0; i < len; ++i ){strcpy( copy, word );for ( int j = i + 1; j <= len; ++j )copy[j - 1] = copy[j];indexWord = Find( copy );if ( indexWord > -1 && InsertWords( copy ) )Ans[ansLen++] = indexWord;}for ( int i = 0; i < len; ++i ){strcpy( copy, word );for ( char w = 'a'; w <= 'z'; ++w ){copy[i] = w;indexWord = Find( copy );if ( indexWord > -1 && InsertWords( copy ) )Ans[ansLen++] = indexWord;}}qsort( Ans, ansLen, sizeof( Ans[0] ), cmp );printf( ":" );for ( int i = 0; i < ansLen; ++i )printf( " %s", hashDic[Ans[i]] );printf( "\n" );}return 0; }
?