题目名称	696. [IOI 1996][USACO 2.3] 最长前缀
输入输出	`prefix.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	6
题目来源	Makazeu 于2012-03-31加入
开放分组	全部用户
提交状态
分类标签	IOI USACO 动态规划字符串字典树/Trie
	分享题解

通过：109，提交：346，通过率：31.5%
LCWhiStLe	100	0.000 s	0.00 MiB	C++
szzy	100	0.000 s	0.00 MiB	C++
szzy	100	0.000 s	0.00 MiB	C++
lihaoze	100	0.004 s	1.01 MiB	C++
Zayin	100	0.007 s	1.27 MiB	C++
李振文	100	0.011 s	0.42 MiB	Pascal
wfff	100	0.013 s	0.88 MiB	C++
Eragon	100	0.014 s	0.50 MiB	C++
栋霸霸	100	0.015 s	105.22 MiB	C++
0	100	0.021 s	0.50 MiB	C++

关于最长前缀的近10条评论(全部评论)
虽说是挺水，但我写了好久...真的弱。。 Fisher. 2017-09-17 17:03 9楼
这题太水辣。我要去参加IOI滑稽不过数据再强点就可以卡STL的常数辣。 Rapiz 2016-03-15 21:31 8楼
用trie来执行查找操作也许会更快吧粘粘自喜 2016-03-14 20:28 7楼
注意控制字符串长度，否则超限 forever 2015-05-04 17:13 6楼
为何如此坑的运行错误！！！！！！ JSX 2014-07-02 17:22 5楼
IOI1996的题。原题中，P的元素个数<=100，P中元素长度<=20 cstdio 2014-01-25 09:47 4楼
/error : ignored the tip "长度为 1..10"/ Truth.Cirno 2012-10-20 00:11 3楼
真水的字符串DP。。。一次AC。。。还最快。。 Makazeu 2012-10-19 21:00 2楼
一定要看好S的输入，否者会吃大亏的！！！！！ hello！ 2012-09-25 20:34 1楼

696. [IOI 1996][USACO 2.3] 最长前缀

★ 输入文件：prefix.in 输出文件：prefix.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

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

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

{A, AB, BA, CA, BBC}

如果序列S前面K个字符可以由某一集合中的元素组成，那么我们就说这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

【输出样例】