P1019 【模板】 子串查找

P1019 【模板】 子串查找

Description

给定一个字符串 \(A\) 和一个字符串 \(B\) ,求 \(B\) 在 \(A\) 中的出现次数。\(A\) 和 \(B\) 中的字符均为英语大写字母或小写字母。

\(A\) 中不同位置出现的 \(B\) 可重叠。

Format

Input

输入共两行,分别是字符串 \(A\) 和字符串 \(B\) 。

Output

输出一个整数,表示 \(B\) 在 \(A\) 中的出现次数。

Sample

Input

zyzyzyz
zyz

Output

3

Limitation

\(1\le A, B\) 的长度 \(\le 10^6, A,B\) 仅包含大小写字母。

信息

难度
9
分类
(无)
标签
递交数
8
已通过
1
通过率
12%
上传者