Longest Prefix 怎么做？ [复制链接]

Longest Prefix
IOI'96
The structure of some biological objects is represented by the sequence of their constituents denoted by uppercase letters. 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 some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan 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.

PROGRAM NAME: prefix
INPUT FORMAT
First, the input file contains the list (length 1..200) of primitives (length 1..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 file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceed 76 letters in length. The "newlines" are not part of the string S.
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC

OUTPUT FORMAT
A single line containing an integer that is the length of the longest prefix that can be composed from the set P.
SAMPLE OUTPUT (file prefix.out)
11


有什么好方法？ＨＥＬＰ！　ＨＥＬＰ！

北极天南星大牛的解答：

动态规划

设dp[i]表示主串S中从i开始的最长的可组成的前缀，dp[1]就是所求，状态转移方程：

dp[i]=max{dp[j]}，其中i到j-1的字串是primitive。

用Hash表判断primitive，将每个primitive转成10位27进制数，在mod一个大质数。在判断primitive的时候只需把i到j-1的字串的Hash值算出来就可以了。

因为primitive最多只有10位，所以时间复杂度是O(10n)，其中n是主串的长度。

感觉他说的不好

好像是：h=max{h[i-len[j]]}+len[j]