#O1045. 模式串匹配

模式串匹配

题目描述

给定文本串 ss 与模式串 pp(均只含小写字母),求 pp 在 ss 中出现的次数(允许重叠)。

题目类型

字符串匹配、KMP

输入格式

第一行一个字符串 ss。

第二行一个字符串 pp。

输出格式

一行一个整数,表示出现次数。

样例 #1

样例输入 #1

abababab
abab

样例输出 #1

3

数据规模与约定

数据范围 说明
$1 \le s
p
  • 朴素匹配最坏 O(∣s∣∣p∣)O(|s||p|) 会超时,请使用 KMP。