Count Pattern Occurrences

Difficulty: Medium · Topic: Strings & pattern matching

Return the number of times pattern occurs in text, counting overlapping occurrences (e.g. "aa" occurs twice in "aaa"). Return 0 for an empty pattern.

Examples

count_occurrences("aaa", "aa")
→ 2

Positions 0 and 1 overlap.

count_occurrences("abababab", "abab")
→ 3

Target complexity: time O(n·m), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.