题目描述

给定一个字符串称之为模式 $p$，再给定一个字符串称之为文本 $t$。请计算 $p$ 是否可以成为 $t$ 的子串，输出 $t$ 有多少种不同位置的子串恰好等于 $p$。

输入格式

• 第一行：单个字符串表示 $p$
• 第二行：单个字符串表示 $t$
• 保证 $p$ 与 $t$ 仅由小写字母构成。

输出格式

• 单个整数：表示答案

aa
aaaab

3

aa
abb

0

数据范围

• $30\%$ 的数据，$1\leq |t|\leq 100$
• $60\%$ 的数据，$1\leq |t|\leq 10000$
• $100\%$ 的数据，$1\leq |p|\leq |t|\leq 300,000$