100 #P1520. *【字符串:hash值】统计字符串出现的次数[Oulipo]

*【字符串:hash值】统计字符串出现的次数[Oulipo]

【题意】

给出两个只由大写字母或小写字母组成的字符串 s1s_1,s2s_2,求 s2s_2s1s_1 中出现多少次。

s1s_1 中不同位置出现的 s2s_2 可重叠。

例如:s1s_1=ABAABA , s2s_2=ABA,答案为 22

【输入格式】

输入共两行,第一行为 s1s1,第二行为 s2s2 (1s1s2106)(1 \le |s_1|,|s_2| \le 10^6)

【输出格式】

一行一个整数,表示答案。

【输入样例】

zyzyzyz
zyz

【输出样例】

3