首页 > 代码库 > poj 1035 Spell checker
poj 1035 Spell checker
题目链接：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; else return 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;}
poj 1035 Spell checker
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。