#P3952. 字符串集合

    ID: 3158 传统题 2000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-二分图建模辅助点压缩边后缀数组Kasai 算法Dinic当前弧优化2014年国家集训队十五人互测

字符串集合

题目描述

有三个字符串集合 prepre、midmid、sufsuf。这里的「集合」可以包含相同的字符串;即使两个字符串内容相同,也视为两个不同的元素。

我们称字符串二元组 (p,q)(p,q) 合法,当且仅当:

  1. pp 是 prepre 中的一个元素;
  2. qq 是 sufsuf 中的一个元素;
  3. 存在 pp 的一个长度不小于 k1k_1 的子串 p′p',qq 的一个长度不小于 k2k_2 的子串 q′q',以及 midmid 中的一个字符串 ss,使得连接后的字符串 p′+q′p'+q' 是 ss 的一个子串。

你可以进行任意次操作。每次操作选择一个合法二元组 (p,q)(p,q),并从 prepre 中删除一个对应元素 pp,从 sufsuf 中删除一个对应元素 qq。

求最多可以进行多少次操作。

注意: 当 k1=0k_1=0 或 k2=0k_2=0 时,允许选择空子串;空子串是任何字符串的子串。

输入格式

第一行包含三个正整数 s1,s2,s3s_1,s_2,s_3,分别表示 prepre、midmid、sufsuf 中的字符串个数。

第二行包含两个非负整数 k1,k2k_1,k_2。

接下来 s1s_1 行,每行一个字符串,依次表示 prepre 的元素。

接下来 s2s_2 行,每行一个字符串,依次表示 midmid 的元素。

接下来 s3s_3 行,每行一个字符串,依次表示 sufsuf 的元素。

输出格式

输出一行一个非负整数,表示最多可以进行的操作次数。

输入输出样例 #1

输入 #1

2 1 4
2 3
aab
bbb
aabbcdd
cdd
bcd
zz
bcde

输出 #1

2

样例解释

合法二元组包括 (aab,bcd)(\texttt{aab},\texttt{bcd})、(aab,bcde)(\texttt{aab},\texttt{bcde}) 和 (bbb,cdd)(\texttt{bbb},\texttt{cdd})。

例如,aabbcdd\texttt{aabbcdd} 包含 aab+bcd\texttt{aab}+\texttt{bcd},也包含 bb+cdd\texttt{bb}+\texttt{cdd}。

字符串 zz 的长度小于 k2=3k_2=3,因此无法与其形成合法二元组。

可以匹配 prepre 中的两个元素,所以答案为 22。

数据规模与约定

定义 len(S)len(S) 为集合 SS 中所有字符串的长度之和,定义

$$K=\max\{s_1,s_2,s_3\},\qquad L=\max\{len(pre),len(mid),len(suf)\}.$$
  • 对于 10%10\% 的数据,K≤5K\le 5,L≤30L\le 30;
  • 对于 20%20\% 的数据,K≤30K\le 30,L≤300L\le 300;
  • 对于 50%50\% 的数据,K≤500K\le 500,L≤104L\le 10^4;
  • 对于 100%100\% 的数据,K≤2.5×104K\le 2.5\times10^4,L≤5×104L\le 5\times10^4,0≤k1,k2≤L0\le k_1,k_2\le L。

所有输入字符串均只包含小写英文字母。