Funcia
Lv.3kmpstring

Pattern Occurrences

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Return how many times pattern occurs in text as a contiguous substring, counting overlapping occurrences ("aa" occurs three times in "aaaa").

Examples

textpatternresult
"abababa""aba"3
"aaaa""aa"3
"abc""abcd"0

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(text: string, pattern: string) → int

Constraints

  • 1≤1 \le text.length ≤1,000,000\le 1{,}000{,}000, 1≤1 \le pattern.length ≤100,000\le 100{,}000
  • Both strings consist of lowercase English letters.

Expected complexity

Time
O(N + M)
Space
O(M)

Examples

textpatternExpected
"abababa""aba"3
"aaaa""aa"3
"abc""abcd"0

Hint

Hint

Use KMP: build the failure function of pattern, scan text keeping the matched length j, and after a full match fall back to fail[j - 1] so overlapping matches are found. O(N+M)O(N + M). Comparing the pattern at every start is O(NM)O(NM) on inputs like "aaa…a", and str.count-style helpers skip overlaps.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.