P1470 [IOI 1996 / USACO2.3] Longest Prefix

In biology, the structures of some organisms are represented by sequences of uppercase letters that contain their components. Biologists are interested in breaking long sequences into shorter sequences (i.e., elements). If the elements in a set $P$ can be concatenated (elements may be reused) to form a sequence $S$, then we say that $S$ can be decomposed into elements from $P$. Not all elements need to appear (for example, `BBC` does not appear below). For instance, the sequence `ABABACABAAB` can be decomposed into elements from the set `{A, AB, BA, CA, BBC}`. The first $k$ characters of sequence $S$ are called the length-$k$ prefix of $S$. Design a program that, given a set of elements and an uppercase-letter sequence, lets $S'$ be the longest prefix of $S$ that can be decomposed into elements from the given set $P$, and computes the length $k$ of $S'$.

The input begins with a set $P$ consisting of several elements, given as a sequence of space-separated strings. All letters are uppercase, and the data may span multiple lines. The set ends with a line that contains only a single `.`. There are no duplicate elements in the set. Then follows the uppercase-letter sequence $S$, given as a string, with a newline after every $76$ characters.

Output a single line containing one integer: the maximum length of a prefix of $S$ that satisfies the condition.

Constraints For $100\%$ of the testdata, $1 \le \text{card}(P) \le 200$, $1 \le |S| \le 2 \times 10^5$, and the length of each element in $P$ does not exceed $10$. Translation from NOCOW. Translated by ChatGPT 5