字符串匹配统计

题目描述

给定一个字符串 a（主串）和一个字符串 b（模式串），请你计算字符串 b 在字符串 a 中出现了多少次。

注意：允许出现位置重叠。

输入格式

输入包含两行： 第一行是字符串 a
第二行是字符串 b

字符串中只包含 数字、大小写英文字母，大小写敏感。

输出格式

输出一行一个整数，表示字符串 b 在字符串 a 中出现的次数。

样例输入

aaaa aa

样例输出

3

数据范围

1 ≤ |b| ≤ |a| ≤ 500000 字符集：0-9, a-z, A-Z

提示

可以使用字符串哈希、KMP 算法等字符串匹配方法。