Trie, Again Trie

Spark Plug Searching, Ltd. wants to build a web-based word processor, and its spell checker stores the dictionary as a binary-encoded trie: a binary tree in which a word is spelled out by walking down the tree one letter at a time, discarding any letter at which you take a right branch.

The end of a word is marked either by a letter that has no left child or by an @ character. The trie shown above contains the words a, abbot, abbey, abed, and bed.

This structure can grow large, but its size can be reduced sharply by exploiting the fact that many words share common suffixes. Scan the trie for identical subtrees: whenever two or more subtrees are identical, all of their parents can be made to point to a single shared copy. Your task is to demonstrate this optimization. Find the shared subtree whose replacement by a single shared copy removes the greatest number of nodes.

If a subtree has $n$ nodes and appears $k$ times, replacing all $k$ copies with one shared copy removes $(k-1)\cdot n$ nodes.

The input consists of one or more lines, each describing one tree. Each tree is given left-justified in preorder, using at least one and at most 200 characters.

• A node is a single lowercase letter or the @ character.
• A # marks the absence of a child in that position.

With these conventions, the preorder description determines the tree uniquely.

The input ends with a line containing the single word END.

For each input tree, print the non-empty subtree (in the same preorder format) that yields the greatest savings when every one of its occurrences is replaced by a single shared copy. On the same line, print a space followed by the number of nodes saved by this replacement. Do not print blank lines between outputs.

If several different subtrees tie for the maximum savings, choose the smallest one (fewest nodes). If a tie still remains, choose the subtree that occurs first in a preorder traversal of the original tree.