KMP string matching algorithm

Problem

Two strings is given to us

• Text(from where we have to find pattern)
• pattern

And we have to find from which index we have same pattern in the text.

The simple solution for this is just run two for loops which has time complexity of  O(m*(m-n+1)) where m is the size of pattern string and n is the size of text string

But KMP can do this in O(n+m) where O(m) for preprocessing and O(n) for searching in the text String

KMP algorithm want axillary array of size m for preprocessing of pattern string this will store matches with the pattern so that you should not always start matching from the starting you can do matching from any index depending upon situation the example is given below

For the pattern “AABAACAABAA”, array[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

here we know that if we got mismatch at index 2 than we should start searching from 1st index not from 0 because there are two A are matched in Text string so one A will definitely match.

When we compare pattern[j] with text[i] and see a mismatch, we know that characters pattern[0..j-1] match with text[i-j+1…i-1] so now we will check array[j-1] and we will start matching from pattern[array[j-1]] and text[i] because of the preprocessing so this algorithm will works in O(n)

Java implementation of this algorithm

https://ideone.com/hcT47E