CF808G Anthem of Berland

Berland 拥有悠久而辉煌的历史。为了让年轻一代更加了解这些历史，Berland 国王决定谱写一首国歌。 虽然 Berland 历史上有许多胜利，但其中有一场最为辉煌。国王希望在国歌中尽可能多地提及这场胜利。 国王已经谱写好了国歌的大部分，现在只需要填写一些字母。国王请求你帮助完成这项工作。 国歌由一个只包含小写英文字母和问号的字符串 $s$ 构成（长度不超过 $10^5$）。最辉煌的胜利由字符串 $t$ 表示（长度不超过 $10^5$）。你需要将字符串 $s$ 中所有的问号替换为小写英文字母，使得字符串 $t$ 在字符串 $s$ 中出现的次数最大。 注意，字符串 $t$ 在 $s$ 中的出现可以重叠。请参考第三个样例进行理解。

第一行包含一个只由小写英文字母和问号组成的字符串 $s$（$1 \le |s| \le 10^5$）。 第二行包含一个仅由小写英文字母组成的字符串 $t$（$1 \le |t| \le 10^5$）。 字符串 $s$ 和 $t$ 的长度乘积不超过 $10^7$。

输出在将字符串 $s$ 中所有问号用小写英文字母替换后，字符串 $t$ 在 $s$ 中最多能出现多少次。

第一个样例中，最终的字符串 $s$ 为 "winlosewinwinlwinwin"。 第二个样例中，最终的字符串 $s$ 为 "glorytoreorand"，字符串最后一个字母可以任意替换。 在第三个样例中，字符串 $t$ 的出现是重叠的。使字符串 $t$ 出现次数最多的 $s$ 是 "abcabcab"。 由 ChatGPT 5 翻译