`
antsmall
  • 浏览: 15657 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
最近访客 更多访客>>
社区版块
存档分类
最新评论

poj 1035 spell checker

J# 
阅读更多

/*
* 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

    【标题】"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中的应用》 在编程竞赛领域,ACM(国际大学生程序设计竞赛)是一项备受瞩目的赛事,它要求参赛者在有限的时间内解决一系列复杂的算法问题。POJ(Problemset Online Judge...

    poj 3435 Sudoku Checker.md

    poj 3435 Sudoku Checker.md

    POJ2586-Y2K Accounting Bug

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

    POJ算法题目分类

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

    poj题目分类

    * 串:例如 poj1035、poj3080、poj1936。 * 排序:例如 poj2388、poj2299。 * 简单并查集的应用。 * 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树...

    poj训练计划.doc

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

    ACM-POJ 算法训练指南

    1. **树和二叉树**:树和二叉树的基本操作和应用(poj1035, poj3080, poj1936)。 2. **堆**:堆排序及其在优先队列中的应用(poj2388, poj2299)。 3. **哈希表**:用于快速查找和存储,如Hash函数的设计(poj3349,...

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

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

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ题目简单分类(ACM)

    - **字符串处理**:如poj1035,涉及字符串操作和模式匹配。 - **排序算法**:包括快速排序、归并排序和堆排序,如poj2388,优化查找效率。 - **并查集**:用于处理集合合并与查询问题。 - **哈希表和二分查找**...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    POJ3253-POJ3253-Fence Repair【STL优先队列】

    标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...

    acm训练计划(poj的题)

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

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    POJ入门题库(含解题思路和答案)

    这些题目是针对ACM竞赛(ACM International Collegiate Programming Contest,简称ICPC)中的编程训练,POJ(Problem Set for Online Judges)是一个在线的编程竞赛平台,提供了许多算法和逻辑思维的练习题目。...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

Global site tag (gtag.js) - Google Analytics