Pattern Matching Using KMP Algorithm
Given a string text and a string pattern, find all starting indices where pattern occurs in text.
Use the Knuth-Morris-Pratt (KMP) algorithm to perform pattern matching efficiently. If the pattern does not occur in the text, return an empty array.
The indices are zero-based and must be returned in ascending order. Overlapping matches should also be included.
Example 1
Input
text = "ababcabcabababd" pattern = "ababd"
Output
[10]
Explanation
The pattern "ababd" occurs in the text starting at index 10.
Example 2
Input
text = "aaaaa" pattern = "aa"
Output
[0, 1, 2, 3]
Explanation
The pattern "aa" occurs at indices 0, 1, 2, and 3. Overlapping matches are included.
Constraints
Hints:
Hint 1
Build an LPS (Longest Proper Prefix that is also a Suffix) array for the pattern.
Hint 2
When a mismatch occurs, use the LPS array to avoid comparing previously matched characters again. Continue searching to find overlapping occurrences.
Author & Technical Reviewer
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output