## IOI '96 P5 - Longest Prefix

View as PDF

Points: 12
Time limit: 1.0s
Memory limit: 32M

Problem type
##### IOI '96 - Veszprém, Hungary

The structure of some biological objects is represented by the sequence of their constituents, where each part is denote by an uppercase letter. Biologists are interested in decomposing a long sequence into shorter ones called primitives.

We say that a sequence can be composed from a given set of primitives if there is a sequence of (possibly repeated) primitives from the set whose concatenation equals . Not necessarily all primitives need be present. For instance the sequence ABABACABAAB can be composed from the set of primitives:

{A, AB, BA, CA, BBC}

The first characters of are the prefix of with length . Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives.

#### Input Specification

First, the input contains the list (length ) of primitives (length ) 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 contains a sequence (length ) expressed as one or more lines, none of which exceeds letters in length. Newline characters are not part of the string .

#### Output Specification

A single line containing an integer that is the length of the longest prefix that can be composed from the set .

#### Sample Input

A AB BA CA BBC
.
ABABACABAABC

#### Sample Output

11