HDU1483《Automatic Correction of Misspellings》

八月 08, 2019 6050

Problem Description

Some text editors offer a feature to correct words which seem to be written incorrectly. In this problem you are asked to implement a simple Automatic Correction of Misspellings (ACM).

ACM takes care of the following misspellings of words:

1.One letter is missing (e.g., letter is written leter) or too much (e.g., letter is written lettter).
2.One letter is wrong (e.g., letter is written ketter)
3.The order of two adjacent letters is wrong (e.g., letter is written lettre)

ACM is based on a dictionary of known words. When a text contains a word which is not in the dictionary, ACM will try to replace it by a similar word of the dictionary. Two words are similar if we can transform one word into the other by doing exactly one of the misspellings listed above. An unknown word is left unchanged if there is no similar word in the dictionary.

Input

The first line of the input file will give the number n of words in the dictionary (n ≤ 10000). The next n lines contain the dictionary words. The following line contains an integer q ≤ 1000, the number of query words. The next q lines contain the query words. You may assume that each word in the input consists of 1 to 25 lower case letters (‘a’ to ‘z’).

Output

For each query word, print one line with the query word followed by one of the following possibilities:

  1. is correct, if the word occurs in the dictionary.
  2. is a misspelling of , where is a word of the dictionary similar to the query word, and the query word is not in the dictionary. In the case that there are several possibilities, select the word from the dictionary which appeared earlier in the input.
  3. is unknown, if cases 1 and 2 do not apply.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
10
this
is
a
dictionary
that
we
will
use
for
us
6
su
as
the
dictonary
us
willl

Sample Output

1
2
3
4
5
6
su is a misspelling of us
as is a misspelling of is
the is unknown
dictonary is a misspelling of dictionary
us is correct
willl is a misspelling of will

解析

还是从代码里复制过来的（

场上写一个 Trie 写到自闭。。。
赛后来补一下

道理我都懂，但是这题为什么暴力能过。。。

以下，将字典中的串称作「字典串」，将询问的串称作「匹配串」

首先扫一遍字典，有相同的直接输出 correct

然后如果没有相同的，再扫一遍字典，对于每一个字典串，做这样几件事：

  1. 如果字典串和匹配串长度相等，就说明这个匹配串可能是当前字典串的一个错误拼写
    逐位扫一遍两个串，记一下错误的次数，以及最后一次错误的下标
    如果错误次数是 1 就直接输出 misspelling，此时匹配串相对于字典串只错了一个字符
    如果错误次数是 2 就判断一下是否是顺序弄反了，这个用最后一次错误下标很好写，如果是就输出 misspelling
    否则就凉凉
  2. 如果字典串比匹配串长 1，就说明这个匹配串可能是当前字典串漏了一个字
    逐位扫一遍字典串，用一个变量 k 记录当前字典串这一位对应的是匹配串的哪一位
    如果当前的两个串对应字符相等，就让 k 正常加一，否则就不让 k 加一
    显然如果真的是只漏了一个字，那么最后 k 一定等于匹配串长度，输出 misspelling
    否则 k 一定不等于匹配串长度（具体会变成什么值我也不大清楚，反正模拟一下就好了）
  3. 如果字典串比匹配串短 1，就说明这个匹配串可能是当前字典串添了一个字
    仿照着情况 2 做就完事了

最后如果三种情况都没有，输出 unknown

代码实现

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//
//  HDU1483.cpp
//  Title: Automatic Correction of Misspellings
//  Debugging
//
//  Created by HandwerSTD on 2019/8/8.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 10000 + 10;

int n, q;
std::string dict[MAXN];
int dictlen[MAXN];

class AutoCorrectionMachine {
public:
    bool isMisspelling(std::string d, std::string m, int len) {
        int wrong = 0, pos = 0;
        for (int i = 0; i < len; ++i) {
            if (d[i] != m[i]) { ++wrong; pos = i; }
        }
        if (wrong == 1) return true;
        if (wrong == 2 && (d[pos] == m[pos - 1] && d[pos - 1] == m[pos])) return true;
        return false;
    }
    bool isCharacterDeletion(std::string d, std::string m, int lend, int lenm) {
        int k = 0;
        for (int i = 0; i < lend; ++i) {
            if (d[i] != m[k++]) --k;
        }
        return k == lenm;
    }
    bool isCharacterAddition(std::string d, std::string m, int lend, int lenm) {
        int k = 0;
        for (int i = 0; i < lenm; ++i) {
            if (m[i] != d[k++]) --k;
        }
        return k == lend;
    }
} acm;

int main() {
    IMPROVE_IO();
    cin >> n;
    rap (i, 1, n, 1) {
        cin >> dict[i];
        dictlen[i] = (int) dict[i].length();
    }
    cin >> q;
    while (q --> 0) {
        std::string env;
        cin >> env;
        int lenenv = (int) env.length();
        cout << env;
        bool cor = false;
        for (int i = 1; i <= n; ++i) if (dict[i] == env) { cor = true; break; }
        if (cor) cout << " is correct\n";
        else {
            int i = 1;
            for (; i <= n; ++i) {
                if (dictlen[i] == lenenv) {
                    if (acm.isMisspelling(dict[i], env, lenenv)) { cout << " is a misspelling of " << dict[i] << endl; break; }
                } else if (dictlen[i] == lenenv + 1) {
                    if (acm.isCharacterDeletion(dict[i], env, dictlen[i], lenenv)) { cout << " is a misspelling of " << dict[i] << endl; break; }
                } else if (dictlen[i] == lenenv - 1) {
                    if (acm.isCharacterAddition(dict[i], env, dictlen[i], lenenv)) { cout << " is a misspelling of " << dict[i] << endl; break; }
                }
            }
            if (i == n + 1) cout << " is unknown\n";
        }
    }
    return 0;
}