题目描述

给定一个字符串 $S$ 和一个模式串 $T$，求 $T$ 在 $S$ 中的出现次数。$S$ 和 $T$ 中的字符均为英语大写字母或小写字母。

$T$ 在 $S$ 中不同位置的出现可以重叠。

输入格式

输入共两行：

• 第一行一个字符串 $S$。
• 第二行一个字符串 $T$。

输出格式

输出一个整数，表示 $T$ 在 $S$ 中的出现次数。

zyzyzyz
zyz

3

样例解释

zyz 在 zyzyzyz 中出现了 $3$ 次，位置可以重叠。

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le |S|, |T| \le 10^6$。
• $S$ 和 $T$ 仅包含大小写字母。