/*
* poj 1035 spell checker
* antsmall
* 10-09-30
* http://poj.org/problem?id=1035
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Word{
char*data;
int seq;
Word(char*d, int s) {
data = d;
seq = s;
}
};
const int MAX_WORD_LEN = 15;
vector<Word*> words[MAX_WORD_LEN+1];
typedef vector<Word*>::iterator veciter;
// 用于排序比较两个字符串,按升序排列
inline bool lessCompStr(const Word*word1, const Word*word2) {
return strcmp(word1->data, word2->data) < 0;
}
// 用来排序word对象,按seq升序排列
inline bool lessCompWord(const Word*word1, const Word*word2) {
return word1->seq < word2->seq;
}
// 在单词表中查找值等于str的,有则true,无则false
bool findSameWord(char str[]) {
int strLen = strlen(str);
int compResult = 0;
for(veciter i = words[strLen].begin(); i != words[strLen].end(); i++) {
compResult = strcmp(str, (*i)->data);
// 结果==0,则相等,返回true
if(compResult == 0)
return true;
// 结果<0, 而且单词表里是按升序排的,那之后都会比str大,所以立即返回false
else if(compResult < 0)
return false;
}
return false;
}
int main()
{
char input[MAX_WORD_LEN+1];
int inputLen = 0;
int seq = 0;
// 单词表输入
while(cin>>input && strcmp(input, "#") != 0) {
inputLen = strlen(input);
char* tmp = new char(inputLen + 1);
strcpy(tmp, input);
words[inputLen].push_back(new Word(tmp, seq));
++seq;
}
// 单词表按字母升序排序
for(int i = 1; i <= MAX_WORD_LEN; i++) {
sort(words[i].begin(), words[i].end(), lessCompStr);
}
vector<Word*> foundWords;
// 要检查的单词输入
while(cin>>input && strcmp(input, "#") != 0) {
foundWords.clear();
// 先查找是否有匹配的,有则打印出来,continue
if(findSameWord(input)) {
printf("%s is correct\n", input);
continue;
}
// 输出单词
printf("%s:", input);
inputLen = strlen(input);
// 查找删除一个字母的
if(inputLen > 1) {
int j = 0, k = 0;
int diff = 0;
for(veciter i = words[inputLen-1].begin(); i != words[inputLen-1].end(); i++) {
j = k = diff = 0;
while (j < inputLen && k < inputLen-1) {
if(input[j] == (*i)->data[k]) {
++j; ++k;
} else {
++j;
++diff;
}
if(diff > 1)
break;
}
if(diff <= 1)
foundWords.push_back(*i);
}
}
// 查找修改一个字母的
{
int j = 0, k = 0;
int diff = 0;
for(veciter i = words[inputLen].begin(); i != words[inputLen].end(); i++) {
j = k = diff = 0;
while (j < inputLen && k < inputLen) {
if((*i)->data[j] != input[k])
++diff;
++j; ++k;
if(diff > 1)
break;
}
if(diff <= 1)
foundWords.push_back(*i);
}
}
// 查找添加一个字母的
if(inputLen < MAX_WORD_LEN) {
int j = 0, k = 0;
int diff = 0;
for(veciter i = words[inputLen+1].begin(); i != words[inputLen+1].end(); i++) {
j = k = diff = 0;
while (j < inputLen+1 && k < inputLen) {
if((*i)->data[j] == input[k]) {
++j; ++k;
} else {
++j;
++diff;
}
if(diff > 1)
break;
}
if(diff <= 1)
foundWords.push_back(*i);
}
}
if(foundWords.size() > 0) {
sort(foundWords.begin(), foundWords.end(), lessCompWord);
for (veciter i = foundWords.begin(); i < foundWords.end(); i++) {
printf(" %s", (*i)->data);
}
}
printf("\n");
}
//system("pause");
return 0;
}
分享到:
相关推荐
【标题】"POJ1035 - Spell checker"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Set of Peking University)。这个题目要求参赛者编写一个拼写检查器,对输入的单词进行错误检测并提供可能的纠正...
"POJ1035-Spell checker 测试数据" 是一个与编程竞赛相关的主题,其中“POJ”是北京大学主办的在线编程平台Problem Online Judge的缩写,它提供了各种算法题目供参赛者挑战。"Spell checker" 指的是这个题目所涉及的...
《多种解题技巧在POJ1035_Spelling Checker中的应用》 在编程竞赛领域,ACM(国际大学生程序设计竞赛)是一项备受瞩目的赛事,它要求参赛者在有限的时间内解决一系列复杂的算法问题。POJ(Problemset Online Judge...
poj 3435 Sudoku Checker.md
【标题】"POJ2586-Y2K Accounting Bug" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。该题目主要关注的是计算机编程中的一个历史问题——Y2K千年虫问题(Year 2000 Problem),同时也涉及到会计...
* 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指解决问题的排序算法,如快排、归并排、堆排。 * 简单并查集:简单并查集是指解决问题的简单并查集算法。 * 哈希表和二分查找...
* 串:例如 poj1035、poj3080、poj1936。 * 排序:例如 poj2388、poj2299。 * 简单并查集的应用。 * 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树...
- 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...
1. **树和二叉树**:树和二叉树的基本操作和应用(poj1035, poj3080, poj1936)。 2. **堆**:堆排序及其在优先队列中的应用(poj2388, poj2299)。 3. **哈希表**:用于快速查找和存储,如Hash函数的设计(poj3349,...
- **例题**:poj1035, poj3080, poj1936 - **解释**:树形数据结构的题目通常涉及树的遍历、查找等问题。 #### 2. 字符串 - **例题**:poj2388, poj2299 - **解释**:字符串问题通常涉及字符串的模式匹配、编辑距离...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
- **字符串处理**:如poj1035,涉及字符串操作和模式匹配。 - **排序算法**:包括快速排序、归并排序和堆排序,如poj2388,优化查找效率。 - **并查集**:用于处理集合合并与查询问题。 - **哈希表和二分查找**...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...
- (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - (poj2388, poj2299):介绍二叉树、平衡二叉树等。 3. **字符串处理**: - (poj3349, poj3274, POJ2151, poj1840, poj2002, poj...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...
这些题目是针对ACM竞赛(ACM International Collegiate Programming Contest,简称ICPC)中的编程训练,POJ(Problem Set for Online Judges)是一个在线的编程竞赛平台,提供了许多算法和逻辑思维的练习题目。...
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...