CF176D.Hyper String

Paul Erdős's prediction came true. Finally an alien force landed on the Earth. In contrary to our expectation they didn't asked the humans to compute the value of a Ramsey number (maybe they had solved it themselves). They asked another question which seemed as hard as calculating Ramsey numbers. Aliens threatened that if humans don't solve this problem in less than 2 hours they will destroy the Earth.

Before telling the problem they introduced the concept of Hyper Strings. A Hyper String is made by concatenation of some base strings. Suppose you are given a list of base strings _b_1, _b_2, ..., b__n. Now the Hyper String made from indices list _i_1, _i_2, ..., i__m is concatenation of base strings _b__i_1, _b__i_2, ..., b__i__m. A Hyper String can be very large and doing operations on it is very costly for computers.

The aliens asked humans to compute the length of the longest common sub-sequence of a Hyper String t with a string s.

保罗·埃尔德什的预言成真了。最终，一支外星力量降临地球。与我们的预期相反，他们并未要求人类计算某个拉姆齐数的值（或许他们自己已经解决了这个问题）。他们提出了另一个看似与计算拉姆齐数一样困难的问题。外星人威胁称：如果人类无法在两小时内解决该问题，他们将摧毁地球。

在提出该问题之前，他们首先介绍了“超字符串”（Hyper String）的概念。超字符串由若干基础字符串拼接而成。假设给定一个基础字符串列表 $b_1,\,b_2,\,\dots,\,b_n$。那么，由下标序列 $i_1,\,i_2,\,\dots,\,i_m$ 构成的超字符串，即为对应基础字符串 $b_{i_1},\,b_{i_2},\,\dots,\,b_{i_m}$ 的拼接结果。超字符串可能非常长，对其执行操作对计算机而言开销极大。

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

The first line of input contains the single integer n (1 ≤ n ≤ 2000) — the number of base strings.

The next n lines contains values of base strings. Each base string is made of lowercase Latin letters. A base string cannot be empty string and the sum of lengths of all n base strings doesn't exceed 106.

The next line contains the single integer m (1 ≤ m ≤ 2000) — the number of base strings in the given Hyper String t.

The next line contains m space-separated integer numbers _i_1, _i_2, ..., i__m (1 ≤ i__j ≤ n) — the indices of base strings in the Hyper String t.

The last line contains a non-empty string s. String s is made of lowercase Latin letters and its length is no more than 2000 characters.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2000$）—— 基础字符串的数量。

接下来的 $n$ 行包含各基础字符串的值。每个基础字符串均由小写拉丁字母组成。基础字符串不能为空，且所有 $n$ 个基础字符串的长度总和不超过 $10^6$。

下一行包含一个整数 $m$（$1 \leq m \leq 2000$）—— 给定超字符串 $t$ 中基础字符串的数量。

再下一行包含 $m$ 个以空格分隔的整数 $i_1,\ i_2,\ \dots,\ i_m$（$1 \leq i_j \leq n$）—— 超字符串 $t$ 中所使用的基础字符串的索引。

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

Print the length of longest common sub-sequence of Hyper String t and string s. If there is no common sub-sequence print 0.

输出超字符串 $t$ 与字符串 $s$ 的最长公共子序列的长度。若不存在公共子序列，则输出 0。

The length of string s is the number of characters in it. If the length of string s is marked as |s|, then string s can be represented as s = _s_1_s_2... s|s|.

A non-empty string y = s[_p_1_p_2... p|y|] = _s__p_1_s__p_2... s__p|y| (1 ≤ _p_1 < _p_2 < ... < p|y| ≤ |s|) is a subsequence of string s. For example, "coders" is a subsequence of "codeforces".

字符串 $s$ 的长度是指其中字符的个数。若字符串 $s$ 的长度记为 $|s|$，则字符串 $s$ 可表示为 $s = s_1 s_2 \dots s_{|s|}$。

非空字符串 $y = s[p_1 p_2 \dots p_{|y|}] = s_{p_1} s_{p_2} \dots s_{p_{|y|}}$（其中 $1 \leq p_1 < p_2 < \dots < p_{|y|} \leq |s|$）称为字符串 $s$ 的一个子序列。例如，“coders” 是 “codeforces” 的一个子序列。