Mhocskian 언어

시간 제한2초메모리 제한512 MB

요약

춤스키 정규형 문맥 자유 문법과 단어 목록이 주어질 때, 시작 변수에서 각 단어가 유도되는지 판정한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열, 구현, 백트래킹
정답자: 아직 제출이 없습니다

문제

언어학자들이 Mhocsky 섬 원주민의 언어인 Mhocskian을 연구하고 있다. 이들은 원주민이 단어를 만드는 방법에 대한 설명과 단어 목록을 발견했고, 그 목록의 단어들 중 어떤 것이 올바른 Mhocskian 단어인지 알고 싶어 한다.

Mhocskian의 단어는 두 종류의 기호로 만들어진다.

변수(variable)는 단어를 만드는 과정에서만 사용되는 대문자이다.
종단 기호(terminal)는 완성된 단어에 실제로 나타나는 소문자이다.

규칙에는 두 종류가 있다.

$V \rightarrow V_1 V_2$ 는 변수 $V$ 를 두 변수 $V_1 V_2$ 로 (그 순서대로) 바꾼다.
$V \rightarrow t$ 는 변수 $V$ 를 종단 기호 $t$ 로 바꾼다.

변수 중 하나는 시작 변수이다. 소문자로 이루어진 단어 $w$ 는, 시작 변수에서 출발하여 규칙들을 차례로 적용해 정확히 $w$ 를 만들어 낼 수 있으면 올바른 Mhocskian 단어이다. 예를 들어 시작 변수가 $S$ 이고 규칙이 $S \rightarrow AB$ , $A \rightarrow a$ , $B \rightarrow b$ 라면, $S \rightarrow AB$ 를 적용한 뒤 $A \rightarrow a$ 와 $B \rightarrow b$ 를 적용하여 단어 $ab$ 를 만들 수 있으므로 $ab$ 는 올바른 단어이다.

규칙과 단어 목록이 주어질 때, 각 단어가 올바른 Mhocskian 단어인지 판별하여라.

입력

첫째 줄에 두 정수 $V$ 와 $T$ 가 주어진다. 각각 변수의 개수와 종단 기호의 개수이다.
둘째 줄에 공백으로 구분된 $V$ 개의 대문자, 즉 변수들이 주어진다. 그중 첫 번째가 시작 변수이다.
셋째 줄에 공백으로 구분된 $T$ 개의 소문자, 즉 종단 기호들이 주어진다.
넷째 줄에 정수 $R_1$ 이 주어진다. 이어지는 $R_1$ 개의 줄은 각각 V t 형태이며 규칙 $V \rightarrow t$ 를 나타낸다.
다음 줄에 정수 $R_2$ 가 주어진다. 이어지는 $R_2$ 개의 줄은 각각 V V1 V2 형태이며 규칙 $V \rightarrow V_1 V_2$ 를 나타낸다.
다음 줄에 정수 $W$ 가 주어진다. 이어지는 $W$ 개의 줄에는 각각 소문자로만 이루어진 단어가 하나씩 주어진다.

출력

$W$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 단어가 올바른 Mhocskian 단어이면 1 을, 그렇지 않으면 0 을 출력한다.

제한

$1 \le V, T \le 26$
$1 \le R_1 + R_2 \le 30$
$1 \le W \le 20$
목록의 각 단어의 길이는 $1$ 이상 $30$ 이하이다.

예제4

예제 1

입력

5 2
I S A B C
a b
2
A a
B b
7
I A B
I A C
C S B
S A B
S A C
I S S
S S S
4
abababaaabbbaabbaabb
abab
bbaa
aaabababbaaabbbb

예상 출력

예제 2

입력

3 2
S A B
a b
3
S a
A a
B b
1
S A B
3
ab
a
b

예상 출력

1
1
0

예제 3
입력
```
1 1
S
a
1
S a
0
2
a
aa
```
예상 출력
```
1
0
```

예제 4

입력

4 2
S X Y Z
a b
4
S a
X a
Y b
Z b
2
S X Y
S S S
8
a
b
ab
ba
aab
abab
abb
baa

예상 출력