题目描述
有三个字符串集合 pre、mid、suf。这里的「集合」可以包含相同的字符串;即使两个字符串内容相同,也视为两个不同的元素。
我们称字符串二元组 (p,q) 合法,当且仅当:
- p 是 pre 中的一个元素;
- q 是 suf 中的一个元素;
- 存在 p 的一个长度不小于 k1 的子串 p′,q 的一个长度不小于 k2 的子串 q′,以及 mid 中的一个字符串 s,使得连接后的字符串 p′+q′ 是 s 的一个子串。
你可以进行任意次操作。每次操作选择一个合法二元组 (p,q),并从 pre 中删除一个对应元素 p,从 suf 中删除一个对应元素 q。
求最多可以进行多少次操作。
注意: 当 k1=0 或 k2=0 时,允许选择空子串;空子串是任何字符串的子串。
输入格式
第一行包含三个正整数 s1,s2,s3,分别表示 pre、mid、suf 中的字符串个数。
第二行包含两个非负整数 k1,k2。
接下来 s1 行,每行一个字符串,依次表示 pre 的元素。
接下来 s2 行,每行一个字符串,依次表示 mid 的元素。
接下来 s3 行,每行一个字符串,依次表示 suf 的元素。
输出格式
输出一行一个非负整数,表示最多可以进行的操作次数。
输入输出样例 #1
输入 #1
2 1 4
2 3
aab
bbb
aabbcdd
cdd
bcd
zz
bcde
输出 #1
2
样例解释
合法二元组包括 (aab,bcd)、(aab,bcde) 和 (bbb,cdd)。
例如,aabbcdd 包含 aab+bcd,也包含 bb+cdd。
字符串 zz 的长度小于 k2=3,因此无法与其形成合法二元组。
可以匹配 pre 中的两个元素,所以答案为 2。
数据规模与约定
定义 len(S) 为集合 S 中所有字符串的长度之和,定义
$$K=\max\{s_1,s_2,s_3\},\qquad L=\max\{len(pre),len(mid),len(suf)\}.$$
- 对于 10% 的数据,K≤5,L≤30;
- 对于 20% 的数据,K≤30,L≤300;
- 对于 50% 的数据,K≤500,L≤104;
- 对于 100% 的数据,K≤2.5×104,L≤5×104,0≤k1,k2≤L。
所有输入字符串均只包含小写英文字母。