Given a text txt[0…n-1] and a pattern pat[0…m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.
Example:
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
The sliding window algorithm would have a window size equal to the length of the pattern.
We would check substrings of length N starting from the left (0 index) to right.
Prefixes and suffixes are used to decrease time complexity.
Psuedo Code:-
while i < n do
{if the characters match}
if pattern[j] = string[i] then do
i ← i + 1
j ← j + 1
{j pointer reached end of pattern}
if j = m then
{matched index}
return i - j
j ← LPS[j - 1]
else if i<n && pattern[j] != string[i] then
{no match}
if j > 0
j ← LPS[j - 1]
else
i ← i + 1
return -1