맥락 없는 인용

선거철이 되면 정치인의 연설이 쏟아진다. 안락의자 평론가인 친구는 정치인의 말을 앞뒤 맥락에서 떼어내 인용하기를 좋아한다. 친구를 도와, 주어진 패턴을 텍스트에서 찾는 방법을 만들어 보자.

텍스트 검색 패턴을 표현하는 강력한 방법 하나가 문맥 자유 문법(context-free grammar, CFG)이다. CFG는 문자열을 생성하며 4-튜플 $(V, \Sigma, R, S)$로 정의한다. $V$는 변수의 집합, $\Sigma$는 종단 기호의 집합, $S \in V$는 시작 변수, $R$은 규칙의 집합이다. $R$의 각 규칙은 다음 형태다.

$V \to (V \cup \Sigma)^*$

규칙의 머리(화살표 왼쪽 변수)는 나타날 때마다 그 규칙의 생성물, 즉 화살표 오른쪽에 있는 변수와 종단 기호의 열로 바꿔 쓸 수 있다. 규칙의 오른쪽은 비어 있어도 된다. 이때는 왼쪽 변수를 빈 문자열로 바꾼다는 뜻이다.

문법은 유도로 종단 기호의 문자열을 생성한다. 유도는 시작 변수 하나만 있는 열에서 출발한다. 변수가 모두 사라질 때까지, 현재 열에 있는 변수 하나를 골라 그 변수의 규칙 중 하나로 바꾸는 과정을 반복한다.

예를 들어 시작 변수가 A인 문법의 규칙(위)과 그 문법의 유도 하나(아래)는 다음과 같다.

A → CFG
C → CC
C → context
F → free
F → FF
G → grammar

A ⇒ CFG
⇒ CCFG
⇒ CcontextFG
⇒ CcontextFFG
⇒ CcontextFFgrammar
⇒ CcontextfreeFgrammar
⇒ contextcontextfreeFgrammar
⇒ contextcontextfreefreegrammar

주어진 CFG가 생성할 수 있는 부분 문자열을 텍스트에서 찾는 프로그램을 작성한다.

이 문제에서 $V$는 영어 대문자의 집합이고 $\Sigma$는 영어 소문자의 집합이다. 입력의 처음에는 CFG의 규칙 집합 $R$이 주어진다. 첫 줄에는 뒤따르는 규칙의 개수 $n$이 주어진다 ($1 \le n \le 30$). 다음 $n$개 줄에는 규칙이 하나씩 다음 형식으로 주어진다.

[A-Z] -> [a-zA-Z]*

즉 대문자 하나, 공백 하나, 화살표, 공백 하나, 그리고 대문자와 소문자로 이루어진 길이 0 이상의 문자열이다. 규칙의 생성물은 길이가 10 이하다. 시작 변수 $S$는 첫 번째 규칙의 머리다.

규칙 다음에는 검색할 텍스트가 최대 100줄 주어지고, 각 줄의 길이는 최대 50이다. 각 줄은 영어 소문자와 공백으로만 이루어지며, 빈 줄이나 공백만 있는 줄도 올 수 있다. 입력은 파일의 끝에서 끝난다.

검색할 각 줄마다, 그 문법이 생성할 수 있는 비어 있지 않은 부분 문자열 중 가장 긴 것을 한 줄에 출력한다. 가장 긴 것이 여러 개면 줄에서 가장 먼저 나오는 것을 출력한다. 그런 부분 문자열이 없으면 대문자로 NONE을 출력한다.