← 返回题目列表

Codeforces · 808/G

G. 贝尔兰国歌

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

Berland有着悠久而辉煌的历史。为了提高年轻公民对此的认识,贝尔兰国王决定创作一首国歌。

虽然贝尔兰德历史上有很多很多的胜利,但其中最引人注目的是一场。金希望在国歌中尽可能多地提及这一点。

他已经创作了国歌的主要部分,现在只需要填写一些字母。金请你帮助他完成这项工作。

国歌是由不超过 105 个小拉丁字母和问号组成的字符串 s。最辉煌的胜利是由不超过105个小拉丁字母组成的字符串t。您应该将所有问号替换为小拉丁字母,以使字符串 t 在字符串 s 中出现的次数最多。

请注意,字符串 t 在 s 中的出现可以重叠。检查第三个示例以进行澄清。

输入

第一行包含小拉丁字母和问号 s 的字符串 (1 ≤ |s| ≤ 105)。

第二行包含小拉丁字母串 t (1 ≤ |t| ≤ 105)。

字符串长度的乘积 |s|·|t|不会超过107。

输出

输出字符串 t 出现的最大次数,将字符串 s 中的所有问号替换为小拉丁字母即可实现。

示例

输入 #1

winlose???winl???w??
win

输出 #1

5

输入 #2

glo?yto?e??an?
or

输出 #2

3

输入 #3

??c?????
abcab

输出 #3

2

注意

在第一个示例中,结果字符串 s 是“winlosewinwinlwinwin”

在第二个示例中,结果字符串 s 是“glorytoreorand”。字符串的最后一个字母可以是任意的。

在第三个示例中,字符串 t 的出现是重叠的。 t 出现次数最多的字符串 s 是“abcabcab”。