Summary
I would like to propose a new utility function patternCount that returns the number of times a substring (pattern) occurs in a string, including overlapping occurrences.
Motivation
Currently, there is no built-in helper for counting overlapping matches efficiently.
A naïve implementation runs in O(n·m), which may be slow for large inputs.
By using the Knuth–Morris–Pratt (KMP) algorithm, we can achieve O(n + m) time complexity.
Example Usage
patternCount("aaaa", "aa"); // 3 (overlapping)
patternCount("abababa", "aba"); // 3
patternCount("hello world", "o"); // 2
Summary
I would like to propose a new utility function
patternCountthat returns the number of times a substring (pattern) occurs in a string, including overlapping occurrences.Motivation
Currently, there is no built-in helper for counting overlapping matches efficiently.
A naïve implementation runs in O(n·m), which may be slow for large inputs.
By using the Knuth–Morris–Pratt (KMP) algorithm, we can achieve O(n + m) time complexity.
Example Usage