IOI '96 P5 - Longest Prefix

View as PDF

Submit solution

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 S can be composed from a given set of primitives P if there is a sequence of (possibly repeated) primitives from the set whose concatenation equals S. 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 K characters of S are the prefix of S with length K. 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 1,\dots,200) of primitives (length 1,\dots,10) 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 S (length 1,\dots,200\,000) expressed as one or more lines, none of which exceeds 76 letters in length. Newline characters are not part of the string S.

Output Specification

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

Sample Input

A AB BA CA BBC
.
ABABACABAABC

Sample Output

11

Comments

There are no comments at the moment.