POJ 1035 - Spell checker

http://poj.org/problem?id=1035

概要

辞書にある \(N\) 個の単語が与えられる。 次に与えられる \(M\) 個の各単語について、辞書に含まれているかどうかを答える。 辞書に含まれていないときは、以下のいずれかの操作を一度だけ行うと与えられた単語になるような辞書中の単語をすべて答える。

• 任意の位置の1文字を消去する
• 任意の位置の1文字を別の1文字に置き換える
• 任意の位置に1文字挿入する

制約

• \(1 \le N \le 10 ^ 4\)
• \(1 \le M \le 50\)
• 単語は小文字のアルファベットのみからなる
• 単語は15文字以下

解法

ちょっと TLE が厳しいけどやるだけ。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct fixed_string
 8 {
 9   char buf[20];
10   int len;
11   bool operator==(const fixed_string& s) const { return strcmp(buf, s.buf) == 0; }
12   const char& operator[](int i) const { return buf[i]; }
13 };
14 
15 bool deleting(const fixed_string& correct, const fixed_string& inp)
16 {
17   const int M = correct.len, N = inp.len;
18   if (N != M+1) {
19     return false;
20   }
21   for (int i = 0; i < N; i++) {
22     if (inp[i] != correct[i]) {
23       fixed_string s;
24       memcpy(s.buf, inp.buf, i);
25       strcpy(s.buf+i, inp.buf+i+1);
26       if (s == correct) {
27         return true;
28       }
29     }
30   }
31   return false;
32 }
33 
34 bool replacing(const fixed_string& correct, const fixed_string& inp)
35 {
36   const int M = correct.len, N = inp.len;
37   if (N != M) {
38     return false;
39   }
40   int c = 0;
41   for (int i = 0; i < N; i++) {
42     if (correct[i] != inp[i]) {
43       ++c;
44     }
45   }
46   return c <= 1;
47 }
48 
49 bool inserting(const fixed_string& correct, const fixed_string& inp)
50 {
51   const int M = correct.len, N = inp.len;
52   if (N+1 != M) {
53     return false;
54   }
55   for (int i = 0; i < M; i++) {
56     if (inp[i] != correct[i]) {
57       fixed_string s;
58       memcpy(s.buf, inp.buf, i);
59       s.buf[i] = correct[i];
60       strcpy(s.buf+i+1, inp.buf+i);
61       if (s == correct) {
62         return true;
63       }
64     }
65   }
66   return false;
67 }
68 
69 int main()
70 {
71   vector<fixed_string> dict;
72   for (fixed_string s; scanf("%s", s.buf) && s.buf[0] != '#';) {
73     s.len = strlen(s.buf);
74     dict.push_back(s);
75   }
76 
77   for (fixed_string s; scanf("%s", s.buf) && s.buf[0] != '#';) {
78     s.len = strlen(s.buf);
79     if (find(dict.begin(), dict.end(), s) != dict.end()) {
80       printf("%s is correct\n", s.buf);
81       continue;
82     }
83 
84     printf("%s:", s.buf);
85     for (vector<fixed_string>::const_iterator it = dict.begin(); it != dict.end(); ++it) {
86       if (deleting(*it, s) || replacing(*it, s) || inserting(*it, s)) {
87         printf(" %s", it->buf);
88       }
89     }
90     putchar('\n');
91   }
92   return 0;
93 }