Count Substring Occurrences | Dataford Interview Questions

Airtel Digital services may scan message text for repeated routing, campaign, or support patterns. Given a text string and a non-empty pattern string, return how many times the pattern occurs in the text, including overlapping occurrences.

Formal Specification

Implement count_substring_occurrences(text, pattern).

text is a string containing the message to scan.
pattern is a non-empty string to search for.
Return an integer representing the number of valid starting positions where pattern matches a substring of text.
Matching is case-sensitive, and occurrences may overlap.

The expected solution should run in linear time using the Knuth-Morris-Pratt pattern-matching technique.

Constraints

0 <= len(text) <= 10^6
1 <= len(pattern) <= 10^5
Both strings contain standard Unicode characters
Matching is case-sensitive
The pattern is guaranteed to be non-empty

Function Signature

def count_substring_occurrences(text, pattern):

Your question is Count Substring Occurrences. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem