String Matching Flashcards
1
Q
Knuth-Morris-Pratt (KMP) Substring matching algorithm is based on which observation?
A
KMP is based on observation as to is there any suffix in the string with also matches the prefix. So for the algorithm to work we need to build LPS (Longest Prefix Same as Suffix). It uses this observation to avoid extra work done while string matching. If a suffix is also appearing in prefix, then we can skip that prefix and start from next index to avoid backtracking and doing repetitive work.
2
Q
What is the time complexity of Naive substring search algorithm? Assuming length of string to be n and length of pattern to be m
A
The worst case time complexity of naive algorithm is O(M.N). Consider the string “aaaaaaab” and pattern “aaab”.
