2297.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2297 on 2006-08-02 at 18:16:06 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
 
struct cmp {
	bool operator()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};
 
map<char*, int, cmp> dict;
char word[10240][32];
 
int main()
{
	int n, q, i, j, k, r;
	
	scanf("%d\n", &n);
	for(i = 0; i < n; i++) {
		gets(word[i]);
		dict[word[i]] = i;
	}
	scanf("%d", &q);
	for(i = 0; i < q; i++) {
		char w[32]; scanf("%s", w);
		if(dict.count(w)) printf("%s is correct\n", w);
		else {
			int o = 10240, l = strlen(w);
			char wo[32];
			for(j = 0; j < l-1; j++) {
				strcpy(wo, w);
				swap(wo[j], wo[j+1]);
				if(dict.count(wo)) o = min(o, dict.find(wo)->second);
			}
			for(j = 0; j <= l; j++) {
				int wn = 0;
				for(k = 0; k <= l; k++) {
					if(k == j) continue;
					wo[wn++] = w[k];
				}
				wo[wn] = 0;
				if(dict.count(wo)) o = min(o, dict.find(wo)->second);
				for(r = 0; r <= 26; r++) {
					wn = 0;
					for(k = 0; k <= l; k++) {
						if(k == j) wo[wn++] = r+'a';
						wo[wn++] = w[k];
					}
					wo[wn] = 0;
					if(dict.count(wo)) o = min(o, dict.find(wo)->second);
					wn = 0;
					for(k = 0; k <= l; k++) {
						if(k == j) wo[wn++] = r+'a';
						else wo[wn++] = w[k];
					}
					wo[wn] = 0;
					if(dict.count(wo)) o = min(o, dict.find(wo)->second);
				}
			}
			if(o == 10240) printf("%s is unknown\n", w);
			else printf("%s is a misspelling of %s\n", w, word[o]);
		}
	}
	
	
	return 0;
}