/*
题意:输入字典,然后输入单词,判断字典中是否出现过该单词,或者是否进行删除、添加、替换操作,如果是,则输出对应的字典中的单词
要求按照输入时候的排名输出
题解:建立两个哈希表。一个存储字典和输入字典中单词的排名,一个进行最后输出的判重
*/
#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;
}
更多详细信息请查看
java教程网 http://www.itchm.com/forum-59-1.html
分享到:
相关推荐
【标题】"POJ1035 - Spell checker"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Set of Peking University)。这个题目要求参赛者编写一个拼写检查器,对输入的单词进行错误检测并提供可能的纠正...
"POJ1035-Spell checker 测试数据" 是一个与编程竞赛相关的主题,其中“POJ”是北京大学主办的在线编程平台Problem Online Judge的缩写,它提供了各种算法题目供参赛者挑战。"Spell checker" 指的是这个题目所涉及的...
总之,"POJ1035_Spelling Checker"这一题目涵盖了模拟法、哈希表、前缀树、Aho-Corasick自动机等多种解题思路,它们各自有其适用场景和优势。在编程竞赛中,掌握并灵活运用这些技巧,不仅能提高解决问题的能力,还能...
poj 3435 Sudoku Checker.md
* 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指解决问题的排序算法,如快排、归并排、堆排。 * 简单并查集:简单并查集是指解决问题的简单并查集算法。 * 哈希表和二分查找...
* 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树:例如 poj3253。 * 堆:例如 poj2513。 * trie 树:例如 poj2513。 4. 简单搜索: * 深度优先搜索...
- 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...
【标题】"POJ2586-Y2K Accounting Bug" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。该题目主要关注的是计算机编程中的一个历史问题——Y2K千年虫问题(Year 2000 Problem),同时也涉及到会计...
3. **哈希表**:用于快速查找和存储,如Hash函数的设计(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503)。 4. **字符串处理**:Trie树(前缀树)的应用(poj2513)。 ### 四、数学算法 1. **数论**:...
- **例题**:poj1035, poj3080, poj1936 - **解释**:树形数据结构的题目通常涉及树的遍历、查找等问题。 #### 2. 字符串 - **例题**:poj2388, poj2299 - **解释**:字符串问题通常涉及字符串的模式匹配、编辑距离...
poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...
例如,题目poj3349和poj3274就涉及到哈希表的应用。 ### 4. 动态规划 动态规划是一种解决多阶段决策问题的方法,通过存储子问题的解来避免重复计算,达到优化的效果。动态规划题目通常要求求解最优解,例如背包...
3. **查找算法**:在哈希表或其他数据结构中查找特定单词,可能需要用到线性查找、二分查找或哈希查找。对于大量数据,高效查找算法是必不可少的。 4. **数据结构**:哈希表或数组可能是存储单词索引的有效数据结构...
- **哈希表和二分查找**:提高查找效率,如poj3349,用于快速定位元素。 - **哈夫曼树**:压缩编码,如poj3253。 - **堆**:如优先队列,用于实现最大值或最小值的快速访问。 - **trie树**:用于高效字符串查询...
2. **构建哈希表**:为了高效地统计每个电话号码出现的次数,可以使用哈希表存储电话号码及其对应的计数。 3. **处理重复电话号码**:遍历哈希表,找出那些出现次数大于1的电话号码及其出现次数,并按要求输出结果。...
* 串算法:POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002、POJ2503 * 哈夫曼树:POJ3253 * 背包问题:POJ1837、POJ1276 * DP算法:POJ3267、POJ1836、...
每次遇到新的个性化号码时,检查它是否已经存在于哈希表中,如果存在则增加对应标准号码的计数,否则添加到哈希表中。 5. **结果输出**:遍历哈希表,找出计数大于1的键值对,即为有多个个性化号码对应的标准号码。...
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
#### 哈希表 高效查找数据的工具,利用哈希函数将数据映射到数组中,如poj3274和POJ2151。 #### 堆 用于维护有序数据结构,如最小堆、最大堆,适用于实现优先队列。 #### 数组与链表 基本的数据存储结构,几乎所有...
- (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - (poj2388, poj2299):介绍二叉树、平衡二叉树等。 3. **字符串处理**: - (poj3349, poj3274, POJ2151, poj1840, poj2002, poj...