【程序设计训练】拼写检查

Myth丶恋晨 2022-11-29 11:59 133阅读 0赞

> 个人思路仅供参考，如有不足欢迎交流。  
> 利用find函数查找相同的字母数量应该也可以通过（没有尝试），但是这样的话遇到字母顺序不同的肯定要出错>\_<

## 【问题描述】 ##

作为一个新的拼写检查程序开发团队的成员，您将编写一个模块，用已知的所有形式正确的词典来检查给定单词的正确性。  
如果字典中没有这个词，那么可以用下列操作中的一个来替换正确的单词（从字典中）：

1.  从单词中删除一个字母；
2.  用一个任意字母替换单词中的一个字母；
3.  在单词中插入一个任意字母。  
    你的任务是编写一个程序，为每个给定的单词找到字典中所有可能的替换。

## 【输入形式】 ##

输入的第一部分包含所有字典中的词，每个单词占用一行，以一个单一字符“\#”作为结束。所有单词都不相同，字典中至多1000个单词。

接下来的部分包含所有需要进行检查的单词，同样每个单词占用一行。这部分也以一个单一字符“\#”作为结束。至多有50个单词需要检查。

在输入中所有的单词（字典中的和需要检查的）都仅由小写字母组成，每个最多包含15个字符。

## 【输出形式】 ##

对于每个在输入中出现的单词，按照它们在输入的第二部分出现的顺序输出一行。如果该单词是正确的（也就是说它包含在字典中）则输出信息：“is correct”；如果该单词不正确，则首先输出该单词，然后输入符号’:’（冒号），之后空一格，写出它所有可能的替代，以空格分隔。这些替代的单词按照它们在字典中（输入的第一部分）出现的顺序写出。如果没有可替代的单词，则在冒号后面直接输出换行。

## 【样例输入】 ##

i
    is
    has
    have
    be
    my
    more
    contest
    me
    too
    if
    award
    #
    me
    aware
    m
    contest
    hav
    oo
    or
    i
    fi
    mre
    #

## 【样例输出】 ##

me is correct
    aware: award
    m: i my me
    contest is correct
    hav: has have
    oo: too
    or:
    i is correct
    fi: i
    mre: more me

## 【提交代码】 ##

（10/10分，C++）

//17.拼写检查
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    void find_simi_ws(string word, vector<string> dictionary);//找到相似的单词
    bool similar(string longone, string shortone);//两个长度相差1的单词是否相似
    
    int main()
    {
        
        string word;//单词
        vector<string> dictionary;//词典
        vector<string>::iterator it;
        while (cin >> word && word[0] != '#')
        {
        
            dictionary.push_back(word);
        }
        while (cin >> word && word[0] != '#')
        {
        
            cout << word;
            bool existence = false;
            for (it = dictionary.begin();it != dictionary.end();it++)
            {
        
                if (*it == word)//在词典中找到word
                {
        
                    existence = true;
                    break;
                }
            }
            if (existence == true)//词典中有word
            {
        
                cout << " is correct" << endl;
            }
            else
            {
        
                cout << ":";
                find_simi_ws(word, dictionary);//寻找与word相似的单词，相似的意思是只有一个字符的差别
            }
        }
        return 0;
    }
    
    void find_simi_ws(string word, vector<string> dictionary)//找到相似的单词
    {
        
        for (unsigned i = 0;i < dictionary.size();i++)
        {
        
            int de = word.length() - dictionary[i].length();//word与dictionary[i]的长度差
            if (de == 0)//长度相等
            {
        
                for (unsigned j = 0;j < word.length();j++)
                {
        
                    if (word[j] != dictionary[i][j])//找到不同的字母
                    {
        
                        string temp = word;
                        temp[j] = dictionary[i][j];//替换不同的字母
                        if (temp == dictionary[i])//变成相同单词
                        {
        
                            cout << ' ' << dictionary[i];
                        }
                        break;//如果没有得到相同单词证明两个词相差不止一个字符，无论如何都要break
                    }
                }
            }
            else if (de == 1)//word比dictionary[i]长1
            {
        
                if (similar(word, dictionary[i]) == true)
                {
        
                    cout << ' ' << dictionary[i];
                }
            }
            else if (de == -1)
            {
        
                if (similar(dictionary[i], word) == true)
                {
        
                    cout << ' ' << dictionary[i];
                }
            }
        }
        cout << endl;
    }
    
    bool similar(string longone, string shortone)
    {
        
        int len_sho = shortone.length();
        string::size_type find_ = longone.find(shortone);
        if(find_!=string::npos)//长的词包含短的词
        {
         
            return true;
        }
        for(int i=0;i<len_sho;i++)
        {
         
            if(shortone[i]!=longone[i])//找到两者首个不同的字符（位置为i）
            {
         
                string temp=shortone.substr(0,i) + longone[i] + shortone.substr(i,len_sho-i);//temp是拼接起来的单词：短的单词0到i位置+长的单词i位置+短的单词i到末尾
                if(temp==longone)
                {
         
                    return true;
                }
                else
                {
        
                    return false;
                }
            }
        }
    }
    /*
    17.Spell_Check-Origin.cpp: In function 'bool similar(std::string, std::string)':
    17.Spell_Check-Origin.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
    }
    ^
    */