트라이, 다시 트라이

Spark Plug Searching, Ltd. 는 웹 기반 워드 프로세서를 만들려고 하며, 맞춤법 검사기는 사전을 이진 인코딩 트라이(binary-encoded trie) 로 저장한다. 이는 이진 트리로, 한 글자씩 아래로 내려가며 단어를 찾되 오른쪽 가지로 내려갈 때 지나온 글자는 버린다.

단어의 끝은 왼쪽 자식이 없는 글자이거나 @ 문자로 표시된다. 위 그림의 트라이에는 단어 a, abbot, abbey, abed, bed 가 들어 있다.

이 구조는 매우 커질 수 있지만, 많은 단어가 공통 접미사를 공유한다는 점을 이용하면 크기를 크게 줄일 수 있다. 트라이에서 동일한 부분 트리(subtree)를 찾아, 서로 같은 부분 트리들의 부모가 모두 하나의 공유 사본을 가리키도록 바꾸면 된다. 이 최적화를 시연하는 것이 과제이다. 모든 인스턴스를 하나의 공유 사본으로 대체했을 때 노드 수가 가장 많이 줄어드는 공유 부분 트리를 찾아라.

어떤 부분 트리가 노드 $n$ 개로 이루어져 있고 $k$ 번 나타난다면, 그 $k$ 개의 사본을 하나의 공유 사본으로 대체할 때 제거되는 노드 수는 $(k-1)\cdot n$ 이다.

입력은 한 줄 이상으로 이루어지며, 각 줄은 트리 하나를 나타낸다. 각 트리는 왼쪽 정렬된 전위 순회(preorder) 형태로 주어지며, 최소 1개에서 최대 200개의 문자를 사용한다.

• 노드는 하나의 소문자 알파벳 또는 @ 문자이다.
• # 는 해당 위치에 자식이 없음을 나타낸다.

이 규칙에 따르면 전위 순회 표현은 트리를 유일하게 결정한다.

입력의 끝은 END 라는 단어만 있는 줄로 표시된다.

각 입력 트리에 대해, 모든 인스턴스를 하나의 공유 사본으로 대체했을 때 절약되는 노드 수가 가장 큰 비어 있지 않은 부분 트리를 (같은 전위 순회 형식으로) 출력한다. 같은 줄에 공백 하나를 두고, 그 대체로 절약되는 노드 수를 출력한다. 출력 사이에 빈 줄을 넣지 않는다.

서로 다른 여러 부분 트리가 최대 절약량에서 동점이면, 그중 가장 작은(노드 수가 가장 적은) 것을 고른다. 그래도 동점이면, 원래 트리의 전위 순회에서 가장 먼저 나타나는 것을 고른다.