공통 부분식 제거

시간 제한1초메모리 제한128 MB

요약

동일한 부분식을 공유하도록 이진 표현식 트리를 최소 DAG로 압축하고, 이전에 등장한 노드를 가리키는 번호로 출력하는 문제입니다.

난이도: 보통10점 중 6점
유형: 해시맵, 트리, 문자열, DFS
정답자: 아직 제출이 없습니다

문제

집합 $\Sigma$ 는 a, b, f, aa, fun, kvqf처럼 소문자 1개에서 4개로 이루어진 모든 단어의 집합이다. 임의의 기호 $f \in \Sigma$ 에 대해, 다음 두 규칙으로 식을 만든다.

$E \rightarrow f$
$E \rightarrow f(E,E)$

모든 식은 그 구문 구조를 그대로 나타내는 트리에 대응된다. 예를 들어 식

a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))

은 노드가 $21$ 개인 트리에 대응된다.

트리 대신 그래프(방향 비순환 그래프)를 사용하면 같은 부분식을 한 번만 저장하고 공유할 수 있어 표현의 크기를 줄일 수 있다. 위 식은 노드가 단 $7$ 개인 그래프로 나타낼 수 있다.

트리 자체도 하나의 그래프이므로 그래프 표현은 유일하지 않다. 주어진 식에 대해, 가능한 한 적은 노드로 그 식을 나타내는 그래프를 구하여라.

입력

첫째 줄에 식의 개수 $c$ ( $1 \le c \le 200$ )가 주어진다. 이어지는 $c$ 개의 줄에는 각각 위 문법을 따르는 식이 공백 없이 하나씩 주어진다. 각 식의 트리 표현은 최대 $50000$ 개의 노드를 가진다.

출력

각 식에 대해, 가능한 한 적은 노드를 사용하는 그래프 표현을 한 줄에 하나씩 출력한다.

그래프 표현은 반복되는 부분식을 숫자로 대체하여 문자열로 적는다. 각 숫자는 그 위치에 넣어야 할 부분식의 루트 노드를 가리킨다. 노드는 처음 적히는 순서대로 $1$ 부터 차례로 번호를 매기며, 이 번호는 그래프에 실제로 나타나는 노드만 세고 숫자로 대체된 자리는 세지 않는다. 숫자는 앞서 이미 적은 노드만 가리킬 수 있으므로, 앞을 가리키는 참조는 존재하지 않는다.

예시 식 a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))의 답은 a(b(f(a,4),b(3,f)),f(2,6))이다.

예제7

예제 1

입력

3
this(is(a,tiny),tree)
a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))
z(zz(zzzz(zz,z),zzzz(zz,z)),zzzz(zz(zzzz(zz,z),zzzz(zz,z)),z))

예상 출력

this(is(a,tiny),tree)
a(b(f(a,4),b(3,f)),f(2,6))
z(zz(zzzz(zz,z),3),zzzz(2,5))

예제 2
입력
```
1
a
```
예상 출력
```
a
```
예제 3
입력
```
1
f(a,b)
```
예상 출력
```
f(a,b)
```
예제 4
입력
```
1
f(a,a)
```
예상 출력
```
f(a,2)
```
예제 5
입력
```
1
g(f(a,a),f(a,a))
```
예상 출력
```
g(f(a,3),2)
```

예제 6

입력

1
k(k(k(a,a),k(a,a)),k(k(a,a),k(a,a)))

예상 출력

k(k(k(a,4),3),2)

예제 7
입력
```
3
a
f(a,b)
z(z,z)
```
예상 출력
```
a
f(a,b)
z(z,2)
```