어간 추출 규칙

Spark Plug Searching, Ltd.의 설계자들은 새 맞춤법 검사기가 사용하는 사전의 크기를 줄이고 싶어 합니다. 이들의 아이디어는 복수형, 과거형 등 여러 문법적 변형을 저장하지 않고 각 단어의 기본 "어간(stem)" 형태만 저장하는 것입니다.

문서에서 어떤 단어를 뽑아 맞춤법을 검사할 때는, 일련의 규칙을 적용해 그 단어를 어간에 가까운 형태로 다시 쓴 뒤, 다시 쓴 단어가 사전에 있는지 확인합니다.

자연어는 불규칙하므로 적절한 규칙 집합을 찾으려면 여러 번 실험해야 합니다. 이를 위해 팀은 다시 쓰기 규칙을 기술하는 간단한 언어를 만들었습니다. 규칙의 형태는 다음과 같습니다.

pattern => replacement

패턴(pattern) 은 하나 이상의 문자로 이루어진 열이며, 각 문자는 다음과 같이 해석됩니다.

• 소문자 알파벳은 단어 안에서 같은 알파벳 한 글자와 일치하며, 대문자와 소문자를 가리지 않습니다. 예를 들어 패턴 ab 는 단어 안의 ab, aB, Ab, AB 와 모두 일치합니다.
• 별표 * 는 알파벳 한 글자 이상과 일치합니다. 패턴에는 별표가 최대 하나만 올 수 있으며, 있다면 반드시 패턴의 첫 글자여야 합니다.
• 대문자 V 는 모음(a, e, i, o, u) 하나와 일치합니다.
• 대문자 C 는 자음(모음이 아닌 알파벳) 하나와 일치합니다.
• 숫자 1-9 는 패턴에서 그 번호 위치의 문자가 일치시킨 것과 같은 문자열과 일치합니다. 이때 패턴의 첫 글자를 1번으로 셉니다. 숫자 k 는 패턴에서 k 번 위치보다 뒤에만 올 수 있습니다.

예를 들어 패턴 *C2ies 는, 같은 자음이 두 번 연달아 나오고 그 뒤에 ies 가 붙는, 길이가 6 이상인 모든 단어와 일치합니다.

규칙의 치환(replacement) 부분은 같은 문자들 중 일부만 사용합니다. 소문자 알파벳은 그대로 옮겨 적고, 숫자는 패턴에서 그 번호가 일치시킨 문자열로 바꿉니다. 예를 들어 규칙

*C2ies => 122y

를 단어 berries 에 적용하면 * 는 be, C 와 2 는 각각 r, ies 는 ies 와 일치합니다. 치환에서 1 은 * 가 일치시킨 be, 각 2 는 r, y 는 그대로 옮겨 적으므로 berries 는 berry 로 다시 쓰입니다.

다시 쓰기 규칙 집합을 읽어 한 문단의 각 단어에 적용하는 프로그램을 작성하세요. 단어 는 연속된 알파벳 문자의 최대 구간입니다. 패턴은 단어 전체와 일치해야 합니다. 각 단어에 대해 주어진 순서대로 규칙을 하나씩 시도하여, 패턴이 일치하거나 규칙이 모두 소진될 때까지 진행합니다. 일치하는 패턴을 찾으면 그 규칙으로 단어를 다시 쓴 뒤 더 이상 규칙을 시도하지 않습니다. 일치하는 규칙이 없으면 단어를 그대로 둡니다.

입력은 여러 개의 데이터 집합으로 이루어집니다. 각 데이터 집합은 위에서 설명한 형식의 규칙 하나 이상으로 시작하며, 규칙은 한 줄에 하나씩 적고 그 뒤에 빈 줄이 옵니다. 이어서 한 줄 이상의 텍스트가 나옵니다. 텍스트는 (다른 데이터 집합이 뒤따를 때는) 빈 줄로 끝나거나, 입력의 끝을 나타내는, 왼쪽에 정렬된 *** 만 있는 줄로 끝납니다.

각 데이터 집합에 대해, 그 규칙에 따라 모든 단어를 다시 쓴 텍스트 줄들을 출력하세요. 단어가 아닌 문자는 그대로 둡니다. 각 데이터 집합의 다시 쓴 텍스트 뒤에는, 왼쪽에 정렬된 *** 만 있는 줄을 한 줄 출력합니다.