List of all the programs for interview
Algorithm - Knuth–Morris–Pratt For String Matching (KMP)
This algorithm solves the problem of finding occurrence of any pattern string within another string or body of text
- It uses a pre-generated table called a
Prefix Table - The prefix table allow us to skip certain comparisions
Text - ACAT ACGACACAGT
Pattern - ACACAGT
Steps :
1- Check the first letter of pattern against the first letter of the text just like naive approach
2- If the pattern mismatches then we will look into the prefix table. The prefix index value will now be aligned with the index which is not matching. Check the image below:
3- The prefix table will give you how much you have shift right.
Generation of Prefix Table
What do you mean by prefix and suffix here
What exactly do we store in the prefix table
At first character we have no possible prefix or suffix, hence the value will 0
At second character we have one prefix and one suffix, and both are not matching hence value will be 0
At third character
At fourth character
At fifth character
At sixth character
At seventh character
Time Complexity of KMP Algorithm
