172. KMP Algorithm or LPS array
Given two strings, one is a text string, text, and the other is a pattern string, pattern. Find and print the indices of all the occurrences of the pattern string within the text string. Use 0-based indexing for the indices, and ensure that the indices are in ascending order. If the pattern does not occur in the text, return an empty list.
Implement this solution using the Knuth-Morris-Pratt (KMP) algorithm for efficient pattern matching.
Example 1:
Input: text = "abracadabra", pattern = "abra"
Output: 0 7
Expalanation : The pattern "abra" appears at the 0st and 7th positions in the text "abracadabra".
Example 2:
Input: text = "abcabcabc", pattern = "abc"
Output: 0 3 6
Expalanation : The pattern "abc" appears at the 0st, 3th, and 6th positions in the text "abcabcabc".
Now Your Turn!
Pick the correct output for the given inputInput: text = "daad", pattern = "aa"
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1<= text.length, pattern.length <=5*104