当前位置:编程学习 > C/C++ >>

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 =
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,