当前位置:首页 > 开发 > 移动开发 > 正文

POJ 1035 Spell checker(哈希表)

发表于: 2012-08-18   作者:aijuans   来源:转载   浏览:
摘要: /* 题意:输入字典,然后输入单词,判断字典中是否出现过该单词,或者是否进行删除、添加、替换操作,如果是,则输出对应的字典中的单词 要求按照输入时候的排名输出 题解:建立两个哈希表。一个存储字典和输入字典中单词的排名,一个进行最后输出的判重 */ #include <iostream> //#define using namespace std; const int HASH =
/*
题意:输入字典,然后输入单词,判断字典中是否出现过该单词,或者是否进行删除、添加、替换操作,如果是,则输出对应的字典中的单词
要求按照输入时候的排名输出

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

#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

POJ 1035 Spell checker(哈希表)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
日期:2013-4-11 来源:GBin1.com Google升级了Chrome网络浏览器的稳定版本,增加了更先进的本地拼
题目地址: http://poj.org/problem?id=2002 题目的大意是在二维平面上有很多点,问有多少种可能组
哈 希 表 传统上,在表中查找一个指定记录的方法都是遍历表中的所有记录直到出现一个匹配的关键字为
哈 希 表 传统上,在表中查找一个指定记录的方法都是遍历表中的所有记录直到出现一个匹配的关键字为
哈希表的有优点很多,最重要的就是速度快。 然而再好的东西也是有缺点的,无疑哈希表是基于数组的,
1. 哈希表的概念    对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关键字所属范
哈希表(HashTable)也叫散列表,是根据关键码值(KeyValue)而直接进行访问的数据结构。它通过把关键
牛文 http://www.cnblogs.com/wangjy/archive/2011/09/08/2171638.html 哈希表是种数据结构,它可以
本篇文章转载 http://www.dnbcw.com/biancheng/java/prek254784.html http://www.javaeye.com/topic
题目链接:http://poj.org/problem?id=1573 http://acm.hdu.edu.cn/showproblem.php?pid=1035 Robot
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号