1.

import java.io.*;
import java.util.*;

/**
* ACM Training 2009 ACM Problem #11048 - Automatic Correction of Misspellings
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8& category=22&page=show_problem&problem=1989
*
* @author Felix Dietrich
* @version 1.0, 09/06/2009
*
* Methode: String matching
* Status : Accepted
* Runtime: 1.900
*/

public class Main
{
public static void main(String... str) throws NumberFormatException, IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<String> dictionary = new ArrayList<String>();
Map<String, String> missingDict = new HashMap<String, String>();
Map<String, String> solutionDict = new HashMap<String, String>();
String word;
/////////////////////7
// READ WORDS

for (int dicWords = Integer.parseInt(br.readLine().trim()); dicWords > 0; dicWords--)
{
word = br.readLine().trim();
dictionary.add(word);
addMissings(missingDict, word);
}

///////////////////////
// READ QUERIES
for (int queries = Integer.parseInt(br.readLine().trim()); queries > 0; queries--)
{
/*
* process queries here.
* Possible missspellings & fixes:
* 1. letter missing: contained in "missingDictionary"
* 2. letter too much: remove letters one after the other and check in "dictionary"
* 3. letter wrong: like 2., but check in "missingDict" and recheck the normal "dictionary"
* 4. two adjacent letters changed: exchange adjacent letters and check in "dictionary"
*/

word = br.readLine().trim();

if (dictionary.contains(word))
System.out.println(word + " is correct");
else
{
solutionDict.clear();

// check removed, wrong or too much letters
letterRemoveCheck(solutionDict, word, dictionary, missingDict);
// check adjacent letters
adjacentCheck(solutionDict, word, dictionary);

if (solutionDict.isEmpty())
System.out.println(word + " is unknown");
else
{
//find solution with minimum input index
int i = Integer.MAX_VALUE;
for (Map.Entry<String, String> me : solutionDict.entrySet())
{
if (dictionary.indexOf(me.getKey()) < i)
{
i = dictionary.indexOf(me.getKey());
word = me.getValue() + me.getKey();
}
}
System.out.println(word);
}
}
}
}

/**
* Checks if the given word is contained in the normal dictionary if two adjacent letters are exchanged.
*
* @param solutionDict
* @param word
* @param dictionary
*/
private static void adjacentCheck(Map<String, String> solutionDict, String word, List<String> dictionary)
{
char[] ca;
char temp;
for (int i = 0; i < word.length() - 1; i++)
{
ca = word.toCharArray();
// exchange two letters.
temp = ca[i];
ca[i] = ca[i + 1];
ca[i + 1] = temp;
if (dictionary.contains(new String(ca)))
{
solutionDict.put(new String(ca), word + " is a misspelling of ");
}
}
}

/**
* Removes one letter after the other and checks if the word is contained in the given dict.
*
* @param solutionDict
* @param word
* @param dictionary
* @param missingDict
* @return true if the word was found
*/
private static void letterRemoveCheck(Map<String, String> solutionDict, String word, List<String> dictionary, Map<String, String> missingDict)
{
StringBuilder sb;
for (int i = 0; i < word.length(); i++)
{
sb = new StringBuilder(word);
sb.deleteCharAt(i);
// letter too much
if (dictionary.contains(sb.toString()))
{
solutionDict.put(sb.toString(), word + " is a misspelling of ");
}
}

//check for wrong letter
for(String correct: dictionary)
{
if(correct.length() == word.length())
{
if(hasOneWrongLetter(correct,word))
{
solutionDict.put(correct, word + " is a misspelling of ");
break;
}
}
}
/*
// if the missing dict contains the new word, we must check if there is
// only one letter wrong (the one we removed).
if (missingDict.containsKey(sb.toString()))
{
sb.insert(i, missingDict.get(sb.toString()).charAt(i));
if (dictionary.contains(sb.toString()))
solutionDict.put(sb.toString(), word + " is a misspelling of ");
}*/

// if one letter is missing, the word is contained in the missing dictionary
if (missingDict.containsKey(word))
{
solutionDict.put(missingDict.get(word), word + " is a misspelling of ");
}
}

/**
* Checks if the word "word" has one wrong letter respecting word "correct".
* word and correct must have same length.
*
* @param correct
* @param word
* @return true if there is only one wrong letter
*/
private static boolean hasOneWrongLetter(String correct, String word)
{
boolean wrongFound = false;
for(int i=0;i<correct.length(); i++)
{
if(correct.charAt(i) != word.charAt(i))
{
if(wrongFound)
{
// indicates we did find more than one wrong letter
wrongFound = false;
break;
}
else
wrongFound = true;
}
}
return wrongFound;
}

/**
* Method for creating words with one letter missing. The word transformed is "word".
*
* @param missingDict dictionary to store the new words in
* @param word word to transform
*/
private static void addMissings(Map<String, String> missingDict, String word)
{
StringBuilder sb;
for (int i = 0; i < word.length(); i++)
{
sb = new StringBuilder(word);
sb.deleteCharAt(i);
if (!missingDict.containsKey(sb.toString()))
missingDict.put(sb.toString(), word);
}
}
}