KMP Notes

Question 1

KMP Main Points

Answer 1

1. Depends on LPS Array (Longest prefix which is also suffix)
2. When there is mismatch in the search string against our pattern then we need not go to the beginning of the search string to again match - worst case is improved here.
3. Now, where do we go when there is mismatch, since there was everything matching before this mismatch so we can move back to some point where match can happen before - which is when the prefix and suffix are same.
4. If we move to some previous point where the prefix and suffix are same then we do not need to match that prefix. Ex. if we have already matched …..abc and there is mismatch after this then we should go to the largest matching prefix before.
5. Start matching again from here. Again repeat from 2.

Question 2

Where to go from mismatch

Answer 2

To the end of largest prefix which matches before mismatch

Question 3

What to do when reached prefix end after mismatch

Answer 3

Try to match again the mismatches. If they match then we need not match something before than this and proceed forward.

Question 4

What is optimization ?

Answer 4

We never match the string which we are already sure of. This surity comes from LPS values, just go back into the pattern where the possible match is possible not in beginning.

In naive algo the failure pushes the pattern to match again while in kmp we go to the point in pattern where the mismatch can be replicated.

Question 5

Time Complexity

Answer 5

O(n + m)

Question 6

Space Complexity

Answer 6

O(p)