POJ 1035 Spell checker(哈希表)

编程技术  /  houtizong 发布于 3年前   108

/*题意：输入字典，然后输入单词，判断字典中是否出现过该单词，或者是否进行删除、添加、替换操作，如果是，则输出对应的字典中的单词要求按照输入时候的排名输出题解：建立两个哈希表。一个存储字典和输入字典中单词的排名，一个进行最后输出的判重*/#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 TESTif(j == 'd'){printf("\n");}#endifif((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;}

更多详细信息请查看java教程网 http://www.itchm.com/forum-59-1.html