`
aijuans
  • 浏览: 1568028 次
社区版块
存档分类
最新评论

POJ 1035 Spell checker(哈希表)

阅读更多
/*
题意:输入字典,然后输入单词,判断字典中是否出现过该单词,或者是否进行删除、添加、替换操作,如果是,则输出对应的字典中的单词
要求按照输入时候的排名输出

题解:建立两个哈希表。一个存储字典和输入字典中单词的排名,一个进行最后输出的判重
*/

#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

    【标题】"POJ1035 - Spell checker"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Set of Peking University)。这个题目要求参赛者编写一个拼写检查器,对输入的单词进行错误检测并提供可能的纠正...

    POJ1035-Spell checker 测试数据

    "POJ1035-Spell checker 测试数据" 是一个与编程竞赛相关的主题,其中“POJ”是北京大学主办的在线编程平台Problem Online Judge的缩写,它提供了各种算法题目供参赛者挑战。"Spell checker" 指的是这个题目所涉及的...

    多种解题技巧POJ1035_Spelling Checker

    总之,"POJ1035_Spelling Checker"这一题目涵盖了模拟法、哈希表、前缀树、Aho-Corasick自动机等多种解题思路,它们各自有其适用场景和优势。在编程竞赛中,掌握并灵活运用这些技巧,不仅能提高解决问题的能力,还能...

    poj 3435 Sudoku Checker.md

    poj 3435 Sudoku Checker.md

    POJ算法题目分类

    * 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指解决问题的排序算法,如快排、归并排、堆排。 * 简单并查集:简单并查集是指解决问题的简单并查集算法。 * 哈希表和二分查找...

    poj题目分类

    * 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树:例如 poj3253。 * 堆:例如 poj2513。 * trie 树:例如 poj2513。 4. 简单搜索: * 深度优先搜索...

    poj训练计划.doc

    - 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...

    POJ2586-Y2K Accounting Bug

    【标题】"POJ2586-Y2K Accounting Bug" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。该题目主要关注的是计算机编程中的一个历史问题——Y2K千年虫问题(Year 2000 Problem),同时也涉及到会计...

    ACM-POJ 算法训练指南

    3. **哈希表**:用于快速查找和存储,如Hash函数的设计(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503)。 4. **字符串处理**:Trie树(前缀树)的应用(poj2513)。 ### 四、数学算法 1. **数论**:...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1035, poj3080, poj1936 - **解释**:树形数据结构的题目通常涉及树的遍历、查找等问题。 #### 2. 字符串 - **例题**:poj2388, poj2299 - **解释**:字符串问题通常涉及字符串的模式匹配、编辑距离...

    acm poj300题分层训练

    poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...

    POJ 分类题目 txt文件

    例如,题目poj3349和poj3274就涉及到哈希表的应用。 ### 4. 动态规划 动态规划是一种解决多阶段决策问题的方法,通过存储子问题的解来避免重复计算,达到优化的效果。动态规划题目通常要求求解最优解,例如背包...

    POJ1496-Word Index

    3. **查找算法**:在哈希表或其他数据结构中查找特定单词,可能需要用到线性查找、二分查找或哈希查找。对于大量数据,高效查找算法是必不可少的。 4. **数据结构**:哈希表或数组可能是存储单词索引的有效数据结构...

    POJ题目简单分类(ACM)

    - **哈希表和二分查找**:提高查找效率,如poj3349,用于快速定位元素。 - **哈夫曼树**:压缩编码,如poj3253。 - **堆**:如优先队列,用于实现最大值或最小值的快速访问。 - **trie树**:用于高效字符串查询...

    POJ 1002 487-3279解题报告

    2. **构建哈希表**:为了高效地统计每个电话号码出现的次数,可以使用哈希表存储电话号码及其对应的计数。 3. **处理重复电话号码**:遍历哈希表,找出那些出现次数大于1的电话号码及其出现次数,并按要求输出结果。...

    ACMer需要掌握的算法讲解 (2).docx

    * 串算法:POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002、POJ2503 * 哈夫曼树:POJ3253 * 背包问题:POJ1837、POJ1276 * DP算法:POJ3267、POJ1836、...

    poj_1002_487.rar_poj 1002

    每次遇到新的个性化号码时,检查它是否已经存在于哈希表中,如果存在则增加对应标准号码的计数,否则添加到哈希表中。 5. **结果输出**:遍历哈希表,找出计数大于1的键值对,即为有多个个性化号码对应的标准号码。...

    poj刷题分类表

    该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友

    poj各种分类

    #### 哈希表 高效查找数据的工具,利用哈希函数将数据映射到数组中,如poj3274和POJ2151。 #### 堆 用于维护有序数据结构,如最小堆、最大堆,适用于实现优先队列。 #### 数组与链表 基本的数据存储结构,几乎所有...

    acm训练计划(poj的题)

    - (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - (poj2388, poj2299):介绍二叉树、平衡二叉树等。 3. **字符串处理**: - (poj3349, poj3274, POJ2151, poj1840, poj2002, poj...

Global site tag (gtag.js) - Google Analytics