← 返回题目列表

Codeforces · 176/D

D. 超字符串

中文机器翻译题面 查看原题

Paul Erdős 的预言成真了。终于,一股外星力量登陆了地球。与我们的预期相反,他们没有要求人类计算拉姆齐数的值(也许他们自己已经解决了)。他们提出了另一个问题,这个问题看起来就像计算拉姆齐数一样困难。外星人威胁说,如果人类不在两个小时内解决这个问题,他们将毁灭地球。

在讲述问题之前,他们介绍了超字符串的概念。超字符串是由一些基本字符串串联而成的。假设给你一个基本字符串列表 b1, b2, ..., bn。现在,由索引列表 i1, i2, ..., im 组成的超字符串是基本字符串 bi1, bi2, ..., bim 的串联。超字符串可能非常大,并且对计算机来说对其进行操作的成本非常高。

外星人要求人类计算超字符串 t 与字符串 s 的最长公共子序列的长度。

输入

输入的第一行包含单个整数 n (1 ≤ n ≤ 2000) — 基本字符串的数量。

接下来的 n 行包含基本字符串的值。每个基本字符串均由小写拉丁字母组成。一个基本字符串不能为空字符串,并且所有n个基本字符串的长度之和不超过106。

下一行包含单个整数 m (1 ≤ m ≤ 2000) — 给定超字符串 t 中基本字符串的数量。

下一行包含 m 个空格分隔的整数 i1, i2, ..., im (1 ≤ ij ≤ n) — 超字符串 t 中基本字符串的索引。

最后一行包含一个非空字符串 s。字符串s由小写拉丁字母组成,长度不超过2000个字符。

输出

打印超字符串 t 和字符串 s 的最长公共子序列的长度。如果没有公共子序列则打印0。

示例

输入 #1

2
cba
dgh
2
1 2
aedfhr

输出 #1

3

输入 #2

2
b
a
5
1 2 1 2 1
aaa

输出 #2

2

注意

字符串 s 的长度是其中的字符数。如果将字符串s的长度标记为|s|,则字符串s可以表示为s = s1s2...s|s|。

非空字符串 y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|) 是字符串 s 的子序列。例如,“coders”是“codeforces”的子序列。