poj1741，poj 1035 Spell checker(hash)

題目鏈接：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;
}

?