OpenJudge

1011:最长前缀(Longest Prefix)

总时间限制:
1000ms
内存限制:
2560kB
描述

在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列(即元素)很感兴趣。

如果一个集合P 中的元素可以通过串联(元素可以重复使用,相当于Pascal 中的“+”运算符)组成一个序列S ,那么我们认为序列S 可以分解为P 中的元素。元素不一定要全部出现(如BBC就没有出现)。举个例子,序列ABABACABAAB 可以分解为下面集合中的元素:

{A, AB, BA, CA, BBC}

序列S 的前面K 个字符称作S 中长度为K 的前缀。设计一个程序,输入一个元素集合以及一个大写字母序列S ,设S'是序列S的最长前缀,使其可以分解为给出的集合P中的元素,求S'的长度K


输入
输入数据的开头包括 1..200 个元素(长度为 1..10 )组成的集合,用连续的以空格分开的字符串表示。字母全部是大写,数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ,长度为 1..200,000 ,用一行或者多行的字符串来表示,每行不超过 76 个字符。换行符并不是序列 S 的一部分。
输出
只有一行,输出一个整数,表示 S 符合条件的前缀的最大长度。
样例输入
A AB BA CA BBC
.
ABABACABAABC
样例输出
11
提示
首先要把题目看懂,简单来说就是给你n个字符串和一个大字符串,问这个大字符串的前多少个可以用这n个字符串拼成,那么很显然,涉及到字符串又涉及到“+“操作,考虑string.

枚举这个大字符串和1~n个小字符串,截取每一段长度看能不能用第i个小字符串覆盖,截取可以用substr函数也可以自己写一个,如果要用第i个小字符串覆盖这一段,那么就要看这个字符串前面的是否被覆盖了,因为是顺推的,用一个数组记录每一截的终点是否被覆盖即可.
来源
USACO译题 2.3.1
全局题号
12141
添加于
2016-11-01
提交次数
17
尝试人数
4
通过人数
1