huring
0%

51nod-1880-单词纠错

Posted on Edited on In

题目：
现在大多数的文本编辑器都的单词究错功能，即你输入的单词不能够在词典中找到的话，他就会建议你修改，然后给出几个候选项。

现在我们就要来写一个生成候选项的算法。

具体算法是这样的，如果输入的单词能够在字典中找到，那么就不用推荐，否则就在字典中找那些能够通过修改一个字母得到目标单词的选项作为推荐。

修改一个字母包括删除一个字母，添加一个字母，以及把单词中的某个位置的字母进行替换。

输入
单组测试数据。
前面若干行给出字典中的单词，每行一个，遇到”#”表示字典中的单词输入结束。
接下来若干行给出用户输入的单词，每行一个，遇到”#”结束。
字典中单词不超过15000个。用户输入的单词不超过60个。每个单词只由小写字母组成，并且非空，长度不超过20。
输出
对于每一个用户的输入，如果在字典中能够找到就输出 “单词 is correct”。否则就输出”单词: 候选1 候选2 …”,候选项按照输入的顺序进行排列。如果找不到候选项，则输出”单词:”。具体可参见样例。
输入样例
样例输入1
i
has
be
more
me
if
^#
me
m
contest
oo
i
^#
输出样例
样例输出1
me is correct
m: i me
contest:
oo:
i is correct
解法:
关键在于如何进行单词匹配，长度相差大于1的可以直接判断为false，长度相差为1的进行处理时，当出现字符不匹配时，选择进行一次删除或者添加操作(效果相同)，长度相同时直接一次判断即可。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
set<string> dict;
set<string> words;
string s[15010];
bool isTrue(string a, string b)
{
    int la = a.length(), lb = b.length();
    if(abs(la - lb) > 1)
        return false;
    if(la == lb){
        int sum = 0;
        for(int i = 0; i < la; i++){
            if(a[i] != b[i])
                sum++;
            if(sum > 1)
                return false;
        }
    }
    else{
        int sum = 0;
        if(lb > la)
            swap(a, b);
        int i = 0 ,j = 0;
        for(int k = 0; k < lb; k++)
        {
            if(a[i++] != b[j++]){
                sum++;
                if(sum == 2)
                    return false;
                j--;lb++;
            }
        }
    }
    return true;
}
int main()
{
    int now = 0 ,sum = 0;
    string str;
    while(cin>>str)
    {

        if(str == "#"){
            now++;
            if(now == 2)
                break;
            continue;
        }
        if(now == 0){
            dict.insert(str);
            s[sum++] = str;
        }
        else{
            if(dict.find(str) != dict.end()){
                cout << str;
                printf(" is correct\n");
            }
            else{
                cout << str << ":";
                for(int i = 0; i < sum; i++){
                    if(isTrue(str,s[i]))
                        cout<<" "<< s[i];
                }
                cout<<endl;
            }
        }
    }
}