题目描述

给一个字符串 T，问在字符串 T 中可以包含最多多少个不重叠的字符串 S 。

字符串中的每个字符为小写或者大写字母。

输入格式

第一行输入一个字符串 S 。

第二行输入一个字符串 T 。

数据范围

50% 的数据，1<= 字符串 T 长度 <= 20000, 1 <= 字符串 S 长度 <= 100

100% 的数据，1<= 字符串 T 长度 <= 1000000, 1<=字符串 S 长度 <= 100000。其中多数是随机产生

输出格式

一个整数表示答案。

样例

Aba
Abababa

1