### 8th International Olympiad in Informatics, Veszprém, Hungary

# IOI'96 Day 2

Problem 2: Longest Prefix

Return to Task Overview
The structure of some biological objects *is* represented
by the sequence of their constituents. These constituents are
denoted by uppercase letters. Biologists are interested in decomposing
a long sequence into shorter ones. These short sequences are called
primitives. We say that a sequence S can be composed from a given
set of primitives P, if there are n primitives p1,...,pn in P
such that the concatenation p1...pn of the primitives equals S.
By the concatenation of primitives p1,...,pn we mean putting
them together in that order without blanks. The same primitive
can occur more than once in the concatenation and not necessarily
all primitives are present. For instance the sequence `ABABACABAAB
`can be composed from the set of primitives

{`A, AB, BA, CA, BBC`}.

The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives P and a sequence of constituents T. The program must compute the length of the longest prefix, that can be composed from primitives in P.

### Input Data

The input data appear in two files. The file `INPUT.TXT` describes
the set of primitives P, while the file `DATA.TXT` contains the
sequence T to be examined. The first line of `INPUT.TXT` contains
N, the number of primitives in P (1<=N<=100). Each primitive
is given in two consecutive lines. The first line contains the
length L of the primitive (1<=L<=20). In the second line
there is a string of uppercase letters (from 'A' to 'Z') of length
L. The N primitives are all different.

Each line of the file `DATA.TXT` contains one uppercase letter in
the first position. This file ends with a line containing a single
period (`'.'`).

The length of the sequence is at least 1 and at most 500,000.

### Output Data

Write into the first line of file `OUTPUT.TXT` the length of the
longest prefix of T that can be composed from the set P.

### Example Input and Output

*Figure 2* gives two input files and a corresponding output file.

INPUT.TXT DATA.TXT OUTPUT.TXT 5 A 11 1 B A A 2 B AB A 3 C BBC A 2 B CA A 2 A BA B C B .

*Figure 2*