POJ 1035 Spell checker(哈希表)

[cpp] 
/*
題意：輸入字典，然後輸入單詞，判斷字典中是否出現過該單詞，或者是否進行刪除、添加、替換操作，如果是，則輸出對應的字典中的單詞
要求按照輸入時候的排名輸出
 
題解：建立兩個哈希表。一個存儲字典和輸入字典中單詞的排名，一個進行最後輸出的判重
*/ 
 
#include <iostream> 
//#define  
using namespace std; 
const int HASH = 12007; 
char list1[HASH][18]; 
int rank[HASH]; 
int head1[HASH]; 
 
char list2[HASH][18]; 
int head2[HASH]; 
 
int ans[10007]; 
int ansLen; 
 
char word[57]; 
char tempWord[57]; 
 
 
int insert1(char *s, int pos) 
{ 
    int len = strlen(s); 
    int i, k = 0; 
    for(i = 0; i < len; ++ i) 
        k = (k * 26 + s[i] - 'a') % HASH; 
    while(head1[k] != 0 && strcmp(list1[k], s) != 0) 
    { 
        k = (k + 1) % HASH; 
    } 
    if(!head1[k]) 
    { 
        head1[k] = 1; 
        strcpy(list1[k], s); 
        rank[k] = pos; 
        return 1; 
    } 
    return 0; 
} 
 
int insert2(char *s) 
{ 
    int len = strlen(s); 
    int i, k = 0; 
    for(i = 0; i < len; ++ i) 
        k = (k * 26 + s[i] - 'a') % HASH; 
    while(head2[k] != 0 && strcmp(list2[k], s) != 0) 
    { 
        k = (k + 1) % HASH; 
    } 
    if(!head2[k]) 
    { 
        head2[k] = 1; 
        strcpy(list2[k], s); 
        return 1; 
    } 
    return 0; 
} 
 
int exist(char *s) 
{ 
    int len = strlen(s); 
    int i, k = 0; 
    for(i = 0; i < len; ++ i) 
        k = (k * 26 + s[i] - 'a') % HASH; 
    while(head1[k] != 0 && strcmp(list1[k], s) != 0) 
    { 
        k = (k + 1) % HASH; 
    } 
    if(!head1[k]) 
    { 
        return -1; 
    } 
    return k; 
} 
 
int cmp(const void *a, const void *b) 
{ 
    int *pa = (int *) a; 
    int *pb = (int *) b; 
    return rank[*pa] - rank[*pb]; 
} 
 
int main() 
{ 
    //int flag = 0; 
    //freopen("e://data.in", "r", stdin); 
    while(gets(word)) 
    { 
        memset(head1, 0, sizeof(head1)); 
         
        int pos = 0; 
        while(word[0] != '#') 
        { 
            insert1(word, pos ++); 
            gets(word); 
        } 
        gets(word); 
        while(word[0] != '#') 
        { 
            memset(head2, 0, sizeof(head2)); 
            ansLen = 0; 
            printf("%s", word); 
            if(exist(word) > -1) 
            { 
                printf(" is correct\n"); 
                gets(word); 
                continue; 
            } 
            int len = strlen(word); 
            int i, k; 
            char j; 
            int z; 
            for(i = 0; i <= len; ++ i) 
            { 
                strcpy(tempWord, word); 
                for(k = len; k >= i; k --) 
                    tempWord[k + 1] = tempWord[k]; 
                for(j = 'a'; j <= 'z'; ++ j) 
                { 
                    tempWord[i] = j; 
                    if((z = exist(tempWord)) > -1 && insert2(tempWord)) 
                    { 
                        ans[ansLen ++] = z; 
                    } 
                } 
            } 
            for(i = 0; i < len; ++ i) 
            { 
                strcpy(tempWord, word); 
                for(k = i + 1; k <= len; ++ k) 
                    tempWord[k - 1] = tempWord[k]; 
                if((z = exist(tempWord)) > -1 && insert2(tempWord)) 
                { 
                    ans[ansLen ++] = z; 
                } 
            } 
            for(i = 0; i < len; ++ i) 
            { 
                strcpy(tempWord, word); 
                for(j = 'a'; j <= 'z'; ++ j) 
                { 
                    tempWord[i] = j; 
#ifdef TEST 
                    if(j == 'd') 
                    { 
                    printf("\n"); 
                    } 
#endif 
                    if((z = exist(tempWord)) > -1 && insert2(tempWord)) 
                    { 
                        ans[ansLen ++] = z; 
                    } 
                } 
            } 
            qsort(ans, ansLen, sizeof(ans[0]), cmp); 
            printf(":"); 
            for(i = 0; i < ansLen; ++ i) 
                printf(" %s", list1[ans[i]]); 
            printf("\n"); 
            gets(word); 
        } 
    } 
    return 0; 
}