Problem D
Lorem Ipsum
You are an archaeologist exploring the underground crypts of Rome. You have just stumbled into a hidden archive containing copies of a lost manuscript by the Knights Templar. Unfortunately, the copies have crumbled over time and now comprise thousands of small text fragments that need to be reassembled in order to restore the original manuscript (or at least a part of it). Because there were several copies of the manuscript, many text fragments overlap with other text fragments. Use a computer to rebuild the manuscript from these fragments! Deus ex machina!
Reconstruction of the manuscript involves placing distinct text fragments in a sequence such that whenever fragment $A$ immediately precedes fragment $B$:
-
$A$ has a suffix that is equal to a prefix of $B$
-
the shared suffix/prefix has length at least $5$
It is guaranteed that two fragments that satisfy these criteria do so in exactly one way.
An optimal reconstruction is one that is extracted from such a sequence of overlapping fragments of maximal length, i.e., a sequence that contains as many fragments as possible. Note that it is the number of fragments that is being maximized here; this may or may not maximize the number of characters in the text that is then recovered from these fragments. (Your archaeologist friends find this a bit odd, but you have an admittedly quirky compulsion to make use of as many found objects as possible.)
Your task is to find an optimal reconstruction. If there are two or more maximal-length sequences of overlapping fragments, then the reconstruction is said to be “ambiguous,” and only a higher power can help. By the grace of that same higher power, no fragment is contained within another fragment, and no sequence of overlapping fragments $F_1, F_2, \ldots , F_ k$, for any $k \geq 2$, ever forms a cycle, i.e., it is never the case that a suffix of $F_ k$ of length $\geq 5$ equals a prefix of $F_1$.
Given a unique maximal-length sequence $F_1, F_2, \ldots , F_ M$, the corresponding optimal reconstruction of the text is
\begin{equation*} F_1 \| \omega (F_2) \| \omega (F_3) \| \ldots \| \omega (F_ M) \end{equation*}where $\| $ denotes string concatenation, and $\omega (F_ i)$ is the substring of $F_ i$ obtained by removing the prefix of length $\geq 5$ that is equal to a suffix of $F_{i-1}$, for $2 \leq i \leq M$.
Input
The first line of input contains an integer $n$ $(1 \leq n \leq 250)$, the number of text fragments. Each of the next $n$ lines contains one of the text fragments. A text fragment is a nonempty string of printable characters of length at most $80$, where a printable character has an ASCII value in the range $32 \ldots 126$, inclusive. All $n$ fragments are distinct, and no fragment begins or ends with a space.
Output
If there is a unique optimal reconstruction, output this reconstruction on a single line. Otherwise, output “AMBIGUOUS”. (No optimal reconstruction ever equals “AMBIGUOUS”.)
| Sample Input 1 | Sample Output 1 |
|---|---|
7 n fox jumps ove uick brown f The quick b y dog. rown fox mps over the l the lazy dog |
The quick brown fox jumps over the lazy dog. |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 cdefghi efghijk efghijx abcdefg |
AMBIGUOUS |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 cdefghix efghijk abcdefghi cdefghij |
abcdefghijk |
