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'$.

First, the input file contains the list $P$ of primitives expressed as a series of space-separated strings of upper-case characters on one or more lines. The list of primitives is terminated by a line that contains nothing more than a period (`.`). No primitive appears twice in the list. Then, the input file contains a sequence $S$ expressed as one or more lines, none of which exceeds $76$ letters in length. The line terminators are not part of the string $S$.

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.