CF176D Hyper String

保罗·埃尔德什的预言成真了。终于有外星势力降临地球。与我们的预期相反，他们并没有要求人类计算 Ramsey 数（也许他们自己已经解决了）。他们提出了另一个看起来和计算 Ramsey 数同样困难的问题。外星人威胁说，如果人类在两小时内解决不了这个问题，他们将摧毁地球。 在给出问题之前，他们引入了“超字符串”（Hyper String）的概念。一个超字符串是通过拼接一些基础字符串（base string）得到的。假设你有一组基础字符串 $b_{1},b_{2},\ldots,b_{n}$。现在，给定一个索引序列 $i_{1},i_{2},\ldots,i_{m}$，则超字符串由这些基础字符串拼接而成，即 $b_{i_1},b_{i_2},\ldots,b_{i_m}$ 的串联。一个超字符串可能非常大，因此对其进行操作在计算机上代价极高。 外星人要求人类计算，超字符串 $t$ 与字符串 $s$ 的最长公共子序列的长度是多少。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示基础字符串的数量。 接下来的 $n$ 行，每行包含一个基础字符串。每个基础字符串由小写英文字母组成，且不能为空字符串。所有 $n$ 个基础字符串长度的总和不超过 $10^{6}$。 接下来一行，包含一个整数 $m$（$1 \leq m \leq 2000$），表示构成超字符串 $t$ 的基础字符串数量。 再下一行包含 $m$ 个以空格分隔的整数 $i_1,i_2,\ldots,i_m$（$1 \leq i_j \leq n$），表示构成超字符串 $t$ 的基础字符串的索引。 最后一行包含一个非空字符串 $s$，由小写英文字母组成，长度不超过 $2000$。

输出超字符串 $t$ 与字符串 $s$ 的最长公共子序列的长度。如果没有公共子序列，输出 $0$。

字符串 $s$ 的长度就是 $s$ 中字符的数量。如果 $s$ 的长度记为 $|s|$，则 $s$ 可以表示为 $s = s_{1}s_{2}...\ s_{|s|}$。 一个非空字符串 $y = s[p_{1}p_{2}\ldots p_{|y|}] = s_{p_1}s_{p_2}\ldots s_{p_{|y|}}$ （$1 \leq p_{1} < p_{2} < \ldots < p_{|y|} \leq |s|$）是字符串 $s$ 的一个子序列。例如，“coders” 是 “codeforces” 的子序列。 由 ChatGPT 5 翻译