← 返回题目列表

Codeforces · 1163/D

D. 神秘代码

中文机器翻译题面 查看原题

在森林里正常散步时,凯蒂偶然发现了一个神秘的代码!然而,神秘的代码中有些字符无法辨认。她将此代码写为字符串 $$$c$$$,由小写英文字符和星号 (“*”) 组成,其中每个星号表示一个不可读的字符。凯蒂对她的发现感到兴奋,她决定通过用任意小写英文字母替换每个星号来恢复不可读的字符(不同的星号可能会替换为不同的字母)。

Katie 有一个最喜欢的字符串 $$$s$$$ 和一个不太喜欢的字符串 $$$t$$$,她很想恢复神秘的代码,以便它尽可能多地出现 $$$s$$$ 并尽可能少地出现 $$$t$$$。正式地,我们将 $$$f(x, y)$$$ 表示为 $$$y$$$ 在 $$$x$$$ 中出现的次数(例如,$$$f(aababa, ab) = 2$$$)。 Katie 想要恢复符合原始 $$$c$$$ 的代码 $$$c'$$$,使得 $$$f(c', s) - f(c', t)$$$ 尽可能最大。然而,凯蒂一般不太擅长恢复密码,所以她希望你能帮助她。

输入

第一行包含字符串 $$$c$$$ ($$$1 \leq |c| \leq 1000$$$) — 神秘代码。保证$$$c$$$仅由小写英文字符和星号“*”组成。

第二行和第三行分别包含字符串 $$$s$$$ 和 $$$t$$$ ($$$1 \leq |s|, |t| \leq 50$$$, $$$s \neq t$$$)。保证 $$$s$$$ 和 $$$t$$$ 仅包含小写英文字符。

输出

打印单个整数 - 恢复代码的 $$$f(c', s) - f(c', t)$$$ 的最大可能值。

示例

输入 #1

*****
katie
shiro

输出 #1

1

输入 #2

caat
caat
a

输出 #2

-1

输入 #3

*a*
bba
b

输出 #3

0

输入#4

***
cc
z

输出#4

2

注意

在第一个示例中,对于 $$$c'$$$ 等于“katie”$$$f(c', s) = 1$$$ 且 $$$f(c', t) = 0$$$,这使得 $$$f(c', s) - f(c', t) = 1$$$ 为最大可能值。

在第二个示例中,唯一符合给定 $$$c$$$ 的 $$$c'$$$ 是“caat”。相应的 $$$f(c', s) - f(c', t) = 1 - 2 = -1$$$。

在第三个示例中,有多种方法可以恢复代码,使得 $$$f(c', s) - f(c', t)$$$ 尽可能最大,例如“aaa”、“aac”甚至“zaz”。对于所有这些恢复的代码,$$$f(c', s) - f(c', t) = 0$$$ 的值。

在第四个示例中,最佳恢复代码$$$c'$$$将是“ccc”。相应的$$$f(c', s) - f(c', t) = 2$$$。