Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Problem 2: Longest Prefix
发信站: 哈工大紫丁香 (2002年03月29日13:55:26 星期五), 站内信件

Problem 2: Longest Prefix
The structure of some biological objects is represented by the sequence of t
heir constituents. These constituents are denoted by uppercase letters. Biol
ogists are interested in decomposing a long sequence into shorter ones. Thes
e short sequences are called primitives. We say that a sequence S can be com
posed 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 con
catenation 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 progr
am which accepts as input a set of primitives P and a sequence of constituen
ts 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 co
ntains 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 primitiv
es are all different.
Each line of the file DATA.TXT contains one uppercase letter in the first po
sition. 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 prefi
x 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
　

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]