33OJ
登录 注册

#P1470. [IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

    ID: 2268 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>字符串动态规划 DPUSACOKMP 算法

[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

Problem Description

In biology, the structures of some organisms are represented by sequences of uppercase letters that contain their components. Biologists are interested in breaking long sequences into shorter sequences (i.e., elements).

If the elements in a set PP can be concatenated (elements may be reused) to form a sequence SS, then we say that SS can be decomposed into elements from PP. Not all elements need to appear (for example, BBC does not appear below). For instance, the sequence ABABACABAAB can be decomposed into elements from the set {A, AB, BA, CA, BBC}.

The first kk characters of sequence SS are called the length-kk prefix of SS. Design a program that, given a set of elements and an uppercase-letter sequence, lets S′S' be the longest prefix of SS that can be decomposed into elements from the given set PP, and computes the length kk of S′S'.

Input Format

First, the input file contains the list PP of primitives 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 SS expressed as one or more lines, none of which exceeds 7676 letters in length. The line terminators are not part of the string SS.

Output Format

Output a single line containing one integer: the maximum length of a prefix of SS that satisfies the condition.

A AB BA CA BBC
.
ABABACABAABC

11

Hint

Constraints

For 100%100\% of the testdata, 1≤card(P)≤2001 \le \text{card}(P) \le 200, 1≤∣S∣≤2×1051 \le |S| \le 2 \times 10^5, and the length of each element in PP does not exceed 1010.

Translation from NOCOW.

Translated by ChatGPT 5.