Demonstrate an example for KMP Algorithm?

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