[IOI1999]隐藏的码字

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file hiddencode.in Output file hiddencode.out

【题目描述】

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

各个字码和该篇文章皆为由英文大小写字母构成的序列。大小写字母是不同的。一个字码的长度(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