子串出现次数

题目描述

给定字符串A和B，问B在A中出现了多少次（可以不连续）。 例如：A="rabbbit", B="rabbit"，A的不同子序列中，有三个与B相同，所以认为B在A中出现了3次。

输入

第一行输入字符串A。 第二行输入字符串B。

输出

B在A中出现的次数。

样例

提示

对50%的数据，A和B的长度不超过100；

对于100%的数据，A和B的数据不超过500.

来源

动规专题