OI题库

【题目描述】

现在有一组字码和一篇文章。该篇文章被认为包含着一个信息，由隐藏在文章中的各个字码以一种奇特的（且可能是暧昧的）方式构成。

各个字码和该篇文章皆为由英文大小写字母构成的序列。大小写字母是不同的。一个字码的长度(length)以平常的方式来定义：例如字码ALL的长度为3。

字码中的各个字母未必连续出现在文章中。举例而言，字码ALL总是出现在文章中的某一个子序列中，其形式为AuLvL，其中u和v是任意的（也可能是空的）字母序列。我们称AuLvL为ALL的一个涵盖序列(covering sequence)。一般而言，一个字码的涵盖序列定义为文章中的一个子序列，其首字母与尾字母和字码的首尾字母相同，且由该子序列中删除某些（可能为零）个字母之后就可得到该字码。应该注意的是，一个字码可以出现在一个或以上的涵盖序列中，也可能根本不出现在文章中。此外，一个涵盖序列也可能同时是好几个字码的的涵盖序列。

一个涵盖序列由它在文章中的起点（其首字母的位置）和终点（其尾字母的位置）来识别。（文章的首字母在位置1上。）我们说两个涵盖序列（例如c1和c2）不相重叠(do not overlap)，如果c1的起点大于(>)c2的终点，或是c2的起点大于c1的终点。否则的话，我们就说这两个涵盖序列重叠(overlap)。

为了要由文章中取出隐藏的信息，你的任务是找到一个解(solution)。一个解由一组项目(items)构成，每个项目均包含一个字码以及该字码的一个涵盖序列，并满足下列各条件：

a)各个涵盖序列互不重叠；

b)一个涵盖序列的长度不会超过1000；

c)各个字码的长度总和达到最大值。（每个项目贡献它所涵盖的字码长度，加成总和。）

你只需求出解中字码长度总和的最大值。

【输入格式】

输入文件的第1行有一个正整数N。接下来的N行各含有一个字码，字码为一串字母，其中不含空白。接下来有一个字母序列（以一个end-of-line字符加一个end-of-file 字符结束）。输入文件中没有空白。

【输出格式】

输出一行一个正整数，即字码长度总和的最大值。

【样例输入】

4

RuN

RaBbit

HoBbit

StoP

StXRuYNvRuHoaBbvizXztNwRRuuNNP

【样例输出】

12

【提示】

样例解释：隐藏的信息可以是：RuN RaBbit RuN，也可以是：RuN HoBbit RuN。

1<=N<=100

字码长度<=100

1<=文章长度<=1000000

我们说字码w的涵盖序列c是右侧极短（right-minimal），如果没有任何c的严格前缀也是w的涵盖序列。所谓c的严格前缀（proper-prefix）指的是不等于c本身的一个c的起始子序列。例如，对字码ALL而言，AAALAL是一个右侧极短的涵盖序列，而AAALALAL虽然也是一个涵盖序列，但并非右侧极短。

所给文章保证以下两点：

a)在文章的任何位置，包含该位置的互相重叠的右侧极短涵盖序列，总数不会超过2500个。

b)右侧极短涵盖序列的总数不会超过10000个。

【来源】

IOI1999 Day 1

翻译来自：http://toi.csie.ntnu.edu.tw/file/20120220154942.pdf