【POJ】1035 Spell checker

时间:2024-08-15 23:03:14

字典树。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std; typedef struct Trie {
int in;
Trie *next[];
} Trie; Trie root;
char map[][];
int nums[], nn; void create(char str[], int in) {
int i = , j, id;
Trie *p = &root, *q; while (str[i]) {
id = str[i] - 'a';
++i;
if (p->next[id] == NULL) {
q = (Trie *)malloc(sizeof(Trie));
q->in = -;
for (j=; j<; ++j)
q->next[j] = NULL;
p->next[id] = q;
}
p = p->next[id];
}
p->in = in;
} int find(char str[], int x) {
int i = , id;
Trie *p = &root; while (str[i]) {
if (i == x) {
++i;
continue;
}
id = str[i] - 'a';
++i;
if (p->next[id] == NULL)
return -;
p = p->next[id];
} return p->in;
} void ffind(char str[]) {
int len = strlen(str), i, j, k;
char ch, bk, bf[];
nn = ; for (i=; i<=len; ++i)
bf[i] = str[i];
for (i=; i<len; ++i) {
bk = bf[i];
for (ch='a'; ch<='z'; ++ch) {
if (ch == bk)
continue;
bf[i] = ch;
j = find(bf, -);
if (j != -)
nums[nn++] = j;
}
bf[i] = bk;
} for (i=; i<len; ++i) {
j = find(bf, i);
if (j != -)
nums[nn++] = j;
}
bf[len+] = '\0';
for (i=; i<=len; ++i) {
k = j = ;
while (j<len) {
if (k != i) {
bf[k] = str[j];
++j;
}
++k;
}
for (ch='a'; ch<='z'; ++ch) {
bf[i] = ch;
j = find(bf, -);
if (j != -)
nums[nn++] = j;
}
}
} int comp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
} int main() {
int n = , f;
char buf[]; for (int i=; i<; ++i)
root.next[i] = NULL; while (scanf("%s", map[n])!=EOF && map[n][]!='#') {
create(map[n], n);
++n;
} while (scanf("%s", buf)!=EOF && buf[]!='#') {
f = find(buf, -);
if (f != -) {
printf("%s is correct\n", buf);
continue;
}
ffind(buf);
printf("%s:", buf);
if (nn) {
qsort(nums, nn, sizeof(int), comp);
for (int i = ; i<nn; ++i) {
if (i && nums[i] == nums[i-])
continue;
printf(" %s", map[nums[i]]);
}
}
printf("\n");
} return ;
}