6518번: 오타 자동 수정

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	148	51	19	30.645%

문제

상근이는 오타를 자동으로 수정해주는 프로그램을 만들려고 한다.

상근이의 프로그램이 고칠 수 있는 오타는 다음과 같은 세 가지 종류이다.

1. 한 글자를 적게 썼을 때 (letter를 leter로 쓴 경우), 한 글자를 많이 썼을 때 (letter를 lettter로 쓴 경우)

2. 한 글자를 잘못 적었을 때 (letter를 ketter로 쓴 경우)

3. 인접한 두 글자의 순서가 잘못 되었을 때 (letter를 lettre로 쓴 경우)

오타 수정 프로그램의 내부에는 단어 사전이 있고, 이 사전을 이용해서 오타를 수정한다. 만약, 사용자가 입력한 단어가 사전에 없는 경우에는, 사전에 있는 단어 중 가장 비슷한 단어로 변경한다. 단어 A를 위의 세 가지 방법 중 하나를 한 번 이용해서 사전에 있는 단어 B로 바꿀 수 있을 때, 두 단어 A와 B를 비슷하다고 한다. 비슷한 단어가 사전에 없는 경우에는 알 수 없는 단어로, 오타 수정을 하지 않는다.

입력

첫째 줄에는 단어 사전에 있는 단어의 수 n이 주어진다. (n ≤ 10000) 다음 n개 줄에는 단어 사전에 있는 단어가 한 줄에 하나씩 주어진다. 다음 줄에는 오타 수정 프로그램을 이용해 수정할 단어의 수 q가 주어진다. (q ≤ 1000) 다음 q개 줄에는 수정할 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자 1개~25개로 이루어져 있다.

출력

각각의 수정할 단어에 대해서, 입력으로 주어진 단어와 아래 세 가지 중 하나를 출력한다.

1. is correct: 단어 사전에 있는 단어인 경우
2. is a misspelling of <x>: 입력으로 주어진 단어가 단어 사전에 없고, <x>가 그 단어와 가장 비슷한 단어일 때. 가능한 <x>가 여러 가지 인 경우에는 입력으로 주어지는 순서가 앞선 것을 출력한다.
3. is unknown: 위의 두 경우가 아닐 때

예제 입력 1

10
this
is
a
dictionary
that
we
will
use
for
us
6
su
as
the
dictonary
us
willl

예제 출력 1

su is a misspelling of us
as is a misspelling of is
the is unknown
dictonary is a misspelling of dictionary
us is correct
willl is a misspelling of will

W3sicHJvYmxlbV9pZCI6IjY1MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWQwYzAgXHVjNzkwXHViM2Q5IFx1YzIxOFx1YzgxNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzYyNFx1ZDBjMFx1Yjk3YyBcdWM3OTBcdWIzZDlcdWM3M2NcdWI4NWMgXHVjMjE4XHVjODE1XHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzYyNFx1ZDBjMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzEzOCBcdWFjMDBcdWM5YzAgXHVjODg1XHViOTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4xLiBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzgwMVx1YWM4YyBcdWMzN2NcdWM3NDQgXHViNTRjIChsZXR0ZXJcdWI5N2MgbGV0ZXJcdWI4NWMgXHVjNGY0IFx1YWNiZFx1YzZiMCksIFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHViOWNlXHVjNzc0IFx1YzM3Y1x1Yzc0NCBcdWI1NGMgKGxldHRlclx1Yjk3YyBsZXR0dGVyXHViODVjIFx1YzRmNCBcdWFjYmRcdWM2YjApPFwvcD5cclxuXHJcbjxwPjIuIFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjNzk4XHViYWJiIFx1YzgwMVx1YzVjOFx1Yzc0NCBcdWI1NGMgKGxldHRlclx1Yjk3YyBrZXR0ZXJcdWI4NWMgXHVjNGY0IFx1YWNiZFx1YzZiMCk8XC9wPlxyXG5cclxuPHA+My4gXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzc5OFx1YmFiYiBcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjIChsZXR0ZXJcdWI5N2MgbGV0dHJlXHViODVjIFx1YzRmNCBcdWFjYmRcdWM2YjApPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1ZDBjMCBcdWMyMThcdWM4MTUgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzBhY1x1YzgwNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNjI0XHVkMGMwXHViOTdjIFx1YzIxOFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YjJlOFx1YzViNFx1YWMwMCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJlNDRcdWMyYjdcdWQ1NWMgXHViMmU4XHVjNWI0XHViODVjIFx1YmNjMFx1YWNiZFx1ZDU1Y1x1YjJlNC4gXHViMmU4XHVjNWI0IEFcdWI5N2MgXHVjNzA0XHVjNzU4IFx1YzEzOCBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjQgQlx1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWIyZThcdWM1YjQgQVx1YzY0MCBCXHViOTdjIFx1YmU0NFx1YzJiN1x1ZDU1OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmU0NFx1YzJiN1x1ZDU1YyBcdWIyZThcdWM1YjRcdWFjMDAgXHVjMGFjXHVjODA0XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViMmU4XHVjNWI0XHViODVjLCBcdWM2MjRcdWQwYzAgXHVjMjE4XHVjODE1XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChuICZsZTsgMTAwMDApIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzYyNFx1ZDBjMCBcdWMyMThcdWM4MTUgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWMyMThcdWM4MTVcdWQ1NjAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOCBxXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHEgJmxlOyAxMDAwKSBcdWIyZTRcdWM3NGMgcVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjODE1XHVkNTYwIFx1YjJlOFx1YzViNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwIDFcdWFjMWN+MjVcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjODE1XHVkNTYwIFx1YjJlOFx1YzViNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHVjNjQwIFx1YzU0NFx1Yjc5OCBcdWMxMzggXHVhYzAwXHVjOWMwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xLiBpcyBjb3JyZWN0OiBcdWIyZThcdWM1YjQgXHVjMGFjXHVjODA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NzggXHVhY2JkXHVjNmIwPGJyIFwvPlxyXG4yLiBpcyBhIG1pc3NwZWxsaW5nIG9mICZsdDt4Jmd0OzogXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIyZThcdWM1YjRcdWFjMDAgXHViMmU4XHVjNWI0IFx1YzBhY1x1YzgwNFx1YzVkMCBcdWM1YzZcdWFjZTAsICZsdDt4Jmd0O1x1YWMwMCBcdWFkZjggXHViMmU4XHVjNWI0XHVjNjQwIFx1YWMwMFx1YzdhNSBcdWJlNDRcdWMyYjdcdWQ1NWMgXHViMmU4XHVjNWI0XHVjNzdjIFx1YjU0Yy4gXHVhYzAwXHViMmE1XHVkNTVjICZsdDt4Jmd0O1x1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjNTVlXHVjMTIwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPGJyIFwvPlxyXG4zLiBpcyB1bmtub3duOiBcdWM3MDRcdWM3NTggXHViNDUwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1NDRcdWIyZDAgXHViNTRjPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNjUxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkF1dG9tYXRpYyBDb3JyZWN0aW9uIG9mIE1pc3NwZWxsaW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+U29tZSB0ZXh0IGVkaXRvcnMgb2ZmZXIgYSBmZWF0dXJlIHRvIGNvcnJlY3Qgd29yZHMgd2hpY2ggc2VlbSB0byBiZSB3cml0dGVuIGluY29ycmVjdGx5LiBJbiB0aGlzIHByb2JsZW0geW91IGFyZSBhc2tlZCB0byBpbXBsZW1lbnQgYSBzaW1wbGUgQXV0b21hdGljIENvcnJlY3Rpb24gb2YgTWlzc3BlbGxpbmdzIChBQ00pLjxcL3A+XHJcblxyXG48cD5BQ00gdGFrZXMgY2FyZSBvZiB0aGUgZm9sbG93aW5nIG1pc3NwZWxsaW5ncyBvZiB3b3Jkczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5PbmUgbGV0dGVyIGlzIG1pc3NpbmcgKGUuZy4sIGxldHRlciBpcyB3cml0dGVuIGxldGVyKSBvciB0b28gbXVjaCAoZS5nLiwgbGV0dGVyIGlzIHdyaXR0ZW4gbGV0dHRlcikuPFwvbGk+XHJcblx0PGxpPk9uZSBsZXR0ZXIgaXMgd3JvbmcgKGUuZy4sIGxldHRlciBpcyB3cml0dGVuIGtldHRlcik8XC9saT5cclxuXHQ8bGk+VGhlIG9yZGVyIG9mIHR3byBhZGphY2VudCBsZXR0ZXJzIGlzIHdyb25nIChlLmcuLCBsZXR0ZXIgaXMgd3JpdHRlbiBsZXR0cmUpPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QUNNIGlzIGJhc2VkIG9uIGEgZGljdGlvbmFyeSBvZiBrbm93biB3b3Jkcy4gV2hlbiBhIHRleHQgY29udGFpbnMgYSB3b3JkIHdoaWNoIGlzIG5vdCBpbiB0aGUgZGljdGlvbmFyeSwgQUNNIHdpbGwgdHJ5IHRvIHJlcGxhY2UgaXQgYnkgYSBzaW1pbGFyIHdvcmQgb2YgdGhlIGRpY3Rpb25hcnkuIFR3byB3b3JkcyBhcmUgc2ltaWxhciBpZiB3ZSBjYW4gdHJhbnNmb3JtIG9uZSB3b3JkIGludG8gdGhlIG90aGVyIGJ5IGRvaW5nIGV4YWN0bHkgb25lIG9mIHRoZSBtaXNzcGVsbGluZ3MgbGlzdGVkIGFib3ZlLiBBbiB1bmtub3duIHdvcmQgaXMgbGVmdCB1bmNoYW5nZWQgaWYgdGhlcmUgaXMgbm8gc2ltaWxhciB3b3JkIGluIHRoZSBkaWN0aW9uYXJ5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgd2lsbCBnaXZlIHRoZSBudW1iZXIgbiBvZiB3b3JkcyBpbiB0aGUgZGljdGlvbmFyeSAobiAmbGU7IDEwMDAwKS4gVGhlIG5leHQgbiBsaW5lcyBjb250YWluIHRoZSBkaWN0aW9uYXJ5IHdvcmRzLiBUaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBxICZsZTsgMTAwMCwgdGhlIG51bWJlciBvZiBxdWVyeSB3b3Jkcy4gVGhlIG5leHQgcSBsaW5lcyBjb250YWluIHRoZSBxdWVyeSB3b3Jkcy4gWW91IG1heSBhc3N1bWUgdGhhdCBlYWNoIHdvcmQgaW4gdGhlIGlucHV0IGNvbnNpc3RzIG9mIDEgdG8gMjUgbG93ZXIgY2FzZSBsZXR0ZXJzICgmIzM5O2EmIzM5OyB0byAmIzM5O3omIzM5Oyk8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnkgd29yZCwgcHJpbnQgb25lIGxpbmUgd2l0aCB0aGUgcXVlcnkgd29yZCBmb2xsb3dlZCBieSBvbmUgb2YgdGhlIGZvbGxvd2luZyBwb3NzaWJpbGl0aWVzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPmlzIGNvcnJlY3QsIGlmIHRoZSB3b3JkIG9jY3VycyBpbiB0aGUgZGljdGlvbmFyeS48XC9saT5cclxuXHQ8bGk+aXMgYSBtaXNzcGVsbGluZyBvZiAmbHQ7eCZndDssIHdoZXJlICZsdDt4Jmd0OyBpcyBhIHdvcmQgb2YgdGhlIGRpY3Rpb25hcnkgc2ltaWxhciB0byB0aGUgcXVlcnkgd29yZCwgYW5kIHRoZSBxdWVyeSB3b3JkIGlzIG5vdCBpbiB0aGUgZGljdGlvbmFyeS4gSW4gdGhlIGNhc2UgdGhhdCB0aGVyZSBhcmUgc2V2ZXJhbCBwb3NzaWJpbGl0aWVzLCBzZWxlY3QgdGhlIHdvcmQgZnJvbSB0aGUgZGljdGlvbmFyeSB3aGljaCBhcHBlYXJlZCBlYXJsaWVyIGluIHRoZSBpbnB1dC48XC9saT5cclxuXHQ8bGk+aXMgdW5rbm93biwgaWYgY2FzZXMgMSBhbmQgMiBkbyBub3QgYXBwbHkuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2006 A번

문제를 번역한 사람: baekjoon

문제

문제

출처

ICPC

6518번 - 오타 자동 수정 다국어

문제

입력

출력

제한

예제 입력 1

예제 출력 1

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

6518번 - 오타 자동 수정 다국어

문제

입력

출력

제한

예제 입력 1 복사

예제 출력 1 복사

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

예제 입력 1

예제 출력 1