允许重叠的匹配

难度：T4

【知识点：KMP字符串匹配】

前置知识：KMP字符串匹配及其冻结前置单元。

题目描述与输入

输入非空文本$s$和模式$p$，均只含小写字母。

输出

输出$p$在$s$中允许重叠的出现次数。

数据范围

$1$<=|$s$|,|$p$|<=$2000$。

样例输入

aaaa
aa

样例输出

3

样例说明

预处理模式前缀函数，失配回退$pi$[$j$-$1$]。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。