【HDOJ】1483 Automatic Correction of Misspellings

水模拟题。
  1 /* 1483 */
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 
  6 #define MAXN 10005
  7 
  8 typedef struct {
  9     char s[26];
 10     int len;
 11 } node_t;
 12 
 13 node_t node[MAXN];
 14 char s[26];
 15 int len, v;
 16 int n, m;
 17 int flag;
 18 
 19 int abs(int x) {
 20     return x<0 ? -x:x;
 21 }
 22 
 23 int min(int a, int b) {
 24     return a<b ? a:b;
 25 }
 26 
 27 int max(int a, int b) {
 28     return a<b ? a:b;
 29 }
 30 
 31 void solve() {
 32     int i, j, k, p, tmp;
 33     int stack[26], top;
 34     flag = 2;
 35     
 36     // check if is correct
 37     for (i=0; flag&&i<n; ++i) {
 38         if (node[i].len==len) {
 39             // swap 2 char or 1 char wrong or just the same
 40             k = 0;
 41             top = 0;
 42             for (j=0; k<=2&&j<len; ++j) {
 43                 if (node[i].s[j] != s[j]) {
 44                     stack[top++] = j;
 45                     ++k;
 46                 }
 47             }
 48             if (k == 0) {
 49                 flag = 0;
 50                 v = i;
 51                 break;
 52             } else if (k==1 && flag>1) {
 53                 flag = 1;
 54                 v = i;
 55             } else if (k==2 && flag>1) {
 56                 if (node[i].s[stack[0]]==s[stack[1]] && node[i].s[stack[1]]==s[stack[0]]) {
 57                     flag = 1;
 58                     v = i;
 59                 }
 60             }
 61         } else if (flag>1 && node[i].len-len==1) {
 62             // one letter is missing
 63             bool st = true;
 64             for (j=k=0; k<node[i].len; ++k) {
 65                 if (node[i].s[k] == s[j])
 66                     ++j;
 67                 else if (st)
 68                     st = false;
 69                 else
 70                     break;
 71             }
 72             if (k >= node[i].len) {
 73                 flag = 1;
 74                 v = i;
 75             }
 76         } else if (flag>1 && len-node[i].len==1) {
 77             // too much
 78             bool st = true;
 79             for (k=0,j=0; j<len; ++j) {
 80                 if (node[i].s[k] == s[j])
 81                     ++k;
 82                 else if (st)
 83                     st = false;
 84                 else
 85                     break;
 86             }
 87             if (j>=len) {
 88                 flag = 1;
 89                 v = i;
 90             }
 91         }
 92     }
 93 }
 94 
 95 int main() {
 96     int i, j, k, tmp;
 97     
 98     #ifndef ONLINE_JUDGE
 99         freopen("data.in", "r", stdin);
100     #endif
101     
102     while (scanf("%d", &n) != EOF) {
103         for (i=0; i<n; ++i) {
104             scanf("%s", node[i].s);
105             node[i].len = strlen(node[i].s);
106         }
107         scanf("%d", &m);
108         while (m--) {
109             scanf("%s", s);
110             len = strlen(s);
111             
112             solve();
113             if (flag == 2)
114                 printf("%s is unknown
", s);
115             else if (flag == 0)
116                 printf("%s is correct
", s);
117             else if (flag == 1)
118                 printf("%s is a misspelling of %s
", s, node[v].s);
119         }
120     }
121     
122     return 0;
123 }