Anthem of Berland

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一个由小写英文字母与问号组成的字符串 $s$，以及一个仅由小写英文字母组成的字符串 $t$。

你需要把 $s$ 中的每个问号替换成任意小写英文字母，使 $t$ 作为连续子串在最终字符串中出现的次数尽可能多。不同出现可以互相重叠。

请输出能够达到的最大出现次数。

输入格式

第一行包含字符串 $s$。

第二行包含字符串 $t$。

输出格式

输出一个整数，表示替换所有问号后 $t$ 的最大出现次数。

样例输入 1

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

样例输出 1

5

样例输入 2

glo?yto?e??an?
or

样例输出 2

3

样例输入 3

??c?????
abcab

样例输出 3

2

数据范围

对于所有测试数据，$1\le |s|,|t|\le 100\,000$，$|s|\cdot |t|\le 10^7$；$s$ 仅含小写英文字母与问号，$t$ 仅含小写英文字母。

提示

样例 3 的一种最优替换是 abcabcab，其中两次出现互相重叠。