철자 추천

철자 추천(spelling suggestion)은 철자 교정 프로그램의 한 부분으로, 잘못 입력했을 가능성이 큰 단어에 대해 그럴듯한 대체 단어를 제안한다. 대체 단어가 얼마나 적절한지는 잘못된 단어와의 편집 거리(edit distance)로 평가할 수 있다. 편집 거리는 한 단어를 다른 단어로 바꾸는 데 필요한 편집 연산들의 총 비용이다.

허용되는 편집 연산과 그 비용은 다음과 같다.

• 삽입: 문자 하나를 끼워 넣는다. 비용 2.
• 삭제: 문자 하나를 지운다. 비용 2.
• 전치(transposition): 인접한 두 문자의 순서를 맞바꾼다. 비용 2.
• 치환: 한 문자를 다른 문자로 바꾼다. 두 문자가 키보드에서 서로 가까우면(근접 치환) 비용 1, 그렇지 않으면(원거리 치환) 비용 2. 같은 문자를 그대로 두면 비용 0.

예를 들어 wonder에서 o를 삭제하면 wnder, o를 a로 치환하면 wander, er를 전치하면 wondre가 된다.

두 단어 사이의 최소 편집 거리는 가능한 모든 연산 순서 중 가장 작은 총 비용이다. 입력 단어와의 최소 편집 거리가 더 작은 사전 단어일수록 더 좋은 철자 추천이다.

어떤 문자 쌍이 서로 가까운지는 (영문 QWERTY 자판을 기준으로 한) 근접 치환 규칙 집합으로 주어진다. 근접 치환은 대칭이다. 즉, 문자 y가 문자 x의 근접 치환 대상으로 주어지면, x를 y로 바꾸는 것과 y를 x로 바꾸는 것 모두 비용이 1이다.

각 입력 단어에 대해, 그 단어와의 최소 편집 거리가 가장 작은 사전 단어(들)를 구하라.

입력은 표준 입력으로 주어지며 세 부분으로 이루어진다. 각 부분은 빈 줄로 끝나므로, 세 번째 부분 뒤의 빈 줄이 입력의 끝을 나타낸다.

첫 번째 부분 — 근접 치환 규칙 (최대 150줄). 각 줄은 공백 하나로 구분된 두 필드로 이루어진다.

• 첫 번째 필드는 한 개의 문자이다.
• 두 번째 필드는 그 문자와 근접 치환할 수 있는 문자들의 나열이다(공백 없음).

근접 치환은 대칭이다. 이 부분에 등장할 수 있는 문자는 일반적인 영문 자판으로 입력할 수 있는 영숫자와 일부 문장 부호이다(공백과 탭 제외).

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()-_=+\|[{]};:',<.>/?

두 번째 부분 — 사전 (최대 150,000개 단어). 한 줄에 한 단어씩 주어진다. 사전 단어는 아래 영문자와 아포스트로피(')로 이루어진다.

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

세 번째 부분 — 검사할 단어 (최대 5,000개 단어). 한 줄에 한 단어씩 주어지며, 첫 번째 부분과 같은 문자 집합을 사용한다.

세 번째 부분의 각 단어에 대해, 콜론(:)으로 구분된 세 필드를 한 줄에 출력한다.

• 입력 단어.
• 입력 단어와 가장 가까운 사전 단어(들) 사이의 최소 편집 거리.
• 그 최소 편집 거리를 달성하는 모든 사전 단어를 오름차순으로, 공백 하나로 구분하여 출력한다. 마지막 단어 뒤에는 공백을 두지 않는다.

정렬은 문자 코드(바이트/ASCII) 순서를 따른다. 따라서 숫자가 대문자보다, 대문자가 소문자보다 앞선다.