题目描述

带有子串包含约束的最长公共子序列问题可以具体表述如下。

给定2个长度分别为n和m的序列X和Y，以及一个子串包含约束集S。

S中共有k个字符串$S=\{S_1,S_2,…,S_k\}$，其中字符串$S_i$的长度为$l_i$，1≤i≤k。带有子串包含约束的最长公共子序列问题就是要找出X和Y的包含约束集S中所有字符串为其子串的最长公共子序列。

例如，如果给定的序列X和Y分别为X=actaagacct, Y=gacctacctc，子串包含约束集S={ata, tact}，则子序列actacct是X和Y的一个无约束的最长公共子序列，而包含约束集S中所有字符串为其子串的一个最长公共子序列是atact 。 在本题中请特别关注子串与子序列的区别。字符串$T=t_1…t_n$的子串是一个形如$T$’$=t_1+i…t_m+i$的字符串，其中，0≤i，m+i≤n。例如，T=abcdefg，则bcd是T 的一个子串，而bce是T的一个子序列，但不是T 的子串。

设计一个算法，找出给定序列X和Y带有子串包含约束S的最长公共子序列。

输入格式

第1行中给出正整数n,m,k，m＜300, n＜300, k＜6。n和m分别表示给定序列X和Y的长度。k表示子串包含约束集S中共有k个字符串。

第2行中有k个整数$l_i$，$0≤l_i≤300,1≤i≤k$，分别表示子串包含约束集S中k个字符串的长度。

第3行和第4行分别给出序列X和Y 。

接下来k行每行一个字符串$S_i$

输出格式

将计算出的X和Y带子串包含约束S的最长公共子序列的长度输出。

10 10 2
3 4
actaagacct
gacctacctc
ata
tact

5

提示

字符串仅包含大小写字母.