POJ 1035 Spell checker 简单字符串匹配

在输入的单词中删除或替换或插入一个字符，看是否在字典中。直接暴力，172ms。。
 1 #include <stdio.h>
 2 #include <string.h>
 3 int len[10000];
 4 char dic[10000][20], s[20];
 5 
 6 bool del(char s1[], char s2[])
 7 {
 8     bool isdel = 0;
 9     for(int i = 0, j = 0; s1[i] && s2[j]; i++, j++)
10     {
11         if(s1[i] != s2[j])
12         {
13             if(isdel)
14                 return 0;
15             j--;
16             isdel = 1;
17         }
18     }
19     return 1;
20 }
21 
22 bool rep(char s1[], char s2[])
23 {
24     bool isrep = 0;
25     for(int i = 0, j = 0; s1[i] && s2[j]; i++, j++)
26     {
27         if(s1[i] != s2[j])
28         {
29             if(isrep)
30                 return 0;
31             isrep = 1;
32         }
33     }
34     return 1;
35 }
36 
37 bool ins(char s1[], char s2[])
38 {
39     bool isins = 0;
40     for(int i = 0, j = 0; s1[i] && s2[j]; i++, j++)
41     {
42         if(s1[i] != s2[j])
43         {
44             if(isins)
45                 return 0;
46             i--;
47             isins = 1;
48         }
49     }
50     return 1;
51 }
52 
53 int main()
54 {
55     int cnt = 0;
56     while(scanf("%s", dic[cnt]) != EOF)
57     {
58         if(dic[cnt][0] == '#')break;
59         len[cnt] = strlen(dic[cnt++]);
60     }
61     while(scanf("%s", s) != EOF)
62     {
63         if(s[0] == '#')break;
64         bool ok = 0;
65         for(int i = 0; i < cnt; i++)
66         {
67             if(strcmp(s, dic[i]) == 0)
68             {
69                 ok = 1;
70                 printf("%s is correct", s);
71             }
72         }
73         if(!ok)
74         {
75             printf("%s:", s);
76             int len_s = strlen(s);
77             for(int i = 0; i < cnt; i++)
78             {
79                 if(len_s - len[i] == 1 && del(s, dic[i]))
80                     printf(" %s", dic[i]);
81                 if(len_s - len[i] == 0 && rep(s, dic[i]))
82                     printf(" %s", dic[i]);
83                 if(len_s - len[i] == -1 && ins(s, dic[i]))
84                     printf(" %s", dic[i]);
85             }
86         }
87         printf("
");
88     }
89     return 0;
90 }
View Code