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;
    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
" );
            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( "
" );
    }

    return 0;
}