1531. [IOI 1999]隐藏的码字

【题目描述】

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

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

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

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

【数据规模与约定】

对于 $20\%$ 的数据，$1 \leq N \leq 22$;

对于 $100\%$ 的数据，$1 \leq N \leq 100,字码长度 \leq 100,1 \leq 文章长度 \leq 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