分数: 600 点
问题陈述
给你两个字符串 S 和 T 由小写英文字母组成。
Takahashi 以字符串开头 S。他可以表演 K 种操作可以任意顺序任意次数。
的 i第操作如下:
支付费用 1。 那么,如果当前字符串包含 字符 C_i,选择其出现之一并将其替换为 字符串 A_i。 否则,什么也不做。
找出使字符串相等所需的最小总成本 T。 如果无法做到这一点,请打印 -1.
约束
- 1\leq |S|\leq |T|\leq 50
- 1\leq K\leq 50
- C_i is
a,b,\ldots,或z. - 1\leq |A_i|\leq 50
- S, T,和 A_i 是由小写英文字母组成的字符串。
- C_i\neq A_i,关于 C_i 作为长度的字符串 1.
- 所有对 (C_i,A_i) 是不同的。
输入
输入由标准输入按以下格式给出:
S T K C_1 A_1 C_2 A_2 \vdots C_K A_K
输出
打印使字符串相等所需的最小总成本 T。 如果无法做到这一点,请打印 -1.
示例输入 1
ab cbca 3 a b b ca a efg
示例输出 1
4
开始于 S=ab,高桥可以制作 T=cbca 四次操作如下:
- 更换 1-st 字符
ainab与b(操作 1-st 种)。字符串现在是bb. - 更换 2-nd 字符
binbb与ca(操作 2-nd 种)。字符串现在是bca. - 更换 1-st 字符
binbca与ca(操作 2-nd 种)。字符串现在是caca. - 更换 2-nd 字符
aincaca与b(操作 1-st 种)。字符串现在是cbca.
每次操作都会产生以下成本 1,总共 4,这是可能的最小值。
示例输入 2
a aaaaa 2 a aa a aaa
示例输出 2
2
两次操作 a \to aaa \to aaaaa 产生的费用为 2,这是可能的最小值。
示例输入 3
a z 1 a abc
示例输出 3
-1
没有操作顺序使得 T=z 来自 S=a.