UVa 11048 - Automatic Correction of Misspellings Solution

import sys
cout=sys.stdout
def chk(s,a):
    ans=len(a)
    sans=""
    b=[]
    for i in range(len(s)+1):
        si=s[:i]
        b.append(si+s[i+1:])
        for j in range(26):
            b.append(si+str(chr(ord('a')+j))+s[i:])
            b.append(si+str(chr(ord('a')+j))+s[i+1:])
            if i<len(s)-1:
                b.append(si+s[i+1]+s[i]+s[i+2:])
    for t in b:
        ky=a.get(t)
        if ky is not None and ky<ans:
            ans=ky
            sans=t
    if ans!=len(a):
        return sans
    return None
def Main():
    n=int(input())
    a={input():0}
    i=1
    for i in range(n-1):
        a[input()]=i
        i+=1
    q=int(input())
    for i in range(q):
        s=input()
        if s in a:
            cout.write(s+" is correct")
        else:
            ts=chk(s,a)
            if ts is not None:
                cout.write(s+" is a misspelling of "+ts)
            else:
                cout.write(s+" is unknown")
        cout.write('\n')
if __name__=="__main__":
    Main()