UVa 11048 - Automatic Correction of Misspellings

// UVa 11048 - Automatic Correction of Misspellings

#include <string>
#include <iostream>
#include <map>
#include <climits>
using namespace std;

int main() {
	int n;
	cin >> n;
	map<string, int> dict;
	for (int i = 1; i <= n; i++) {
		string word;
		cin >> word;
		dict[word] = i;
	}
	int q;
	for (cin >> q; q; q--) {
		string word;
		cin >> word;
		int len = word.length();
		if (dict[word]) {
			cout << word << " is correct" << endl;
			continue;
		}
		int best = INT_MAX;
		string sol;
		for (int i = 0; i < len; i++) {
			// without this char
			string probableWord = word.substr(0, i)
					+ word.substr(i + 1, len - i - 1);
			if (dict[probableWord] != 0 && dict[probableWord] < best) {
				best = dict[probableWord];
				sol = probableWord;
			}
			// swap chars
			if (i + 1 < len) {
				probableWord = word;
				char tmp = probableWord[i];
				probableWord[i] = probableWord[i + 1];
				probableWord[i + 1] = tmp;
				if (dict[probableWord] != 0 && dict[probableWord] < best) {
					best = dict[probableWord];
					sol = probableWord;
				}
			}

			for (char ch = 'a'; ch <= 'z'; ch++) {
				// this char is wrong
				probableWord = word;
				probableWord[i] = ch;
				if (dict[probableWord] != 0 && dict[probableWord] < best) {
					best = dict[probableWord];
					sol = probableWord;
				}
				// adding a char
				probableWord = word.substr(0, i) + ch + word.substr(i, len - i);
				if (dict[probableWord] != 0 && dict[probableWord] < best) {
					best = dict[probableWord];
					sol = probableWord;
				}
			}
		}

		// adding a char at the end
		for (char ch = 'a'; ch <= 'z'; ch++) {
			string probableWord = word + ch;
			if (dict[probableWord] != 0 && dict[probableWord] < best) {
				best = dict[probableWord];
				sol = probableWord;
			}
		}

		if (best == INT_MAX)
			cout << word << " is unknown" << endl;
		else
			cout << word << " is a misspelling of " << sol << endl;
	}

	return 0;
}