Knuth–Morris–Pratt (KMP) Pattern Matching Substring Search - First Occurrence Of Substring

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: Given a string s and a pattern p, determine if the pattern exists in the string. Return the index of where the first occurrence starts. Further Explanation From Tuschar Roy: https://www.youtube.com/watch?v=GTJr8OvyEVQ The Brute Force The naive approach to solving this is looking in s for the first character in p. If a match is found we begin a search from that index, call it i (for intersect). We compare the 2nd character of p with index i + 1 of s We compare the 3rd character of p with index i + 2 of s ...and so on until we have matched to all of p without either having overrun s or having found a mismatch between characters being compared. We can then return i as our answer. It doesn’t work well in cases where we see many matching characters followed by a mismatching character. Complexities: Time: O( len(s) * len(p) ) In a simple worst case we can have s = "aaaaaab" p = "aaab" The problem is that for each first character match we have the potential to naively go into a search on a string that would never yield a correct answer repeatedly. Other Algorithms There are three linear time string matching algorithms: KMP (nuth–Morris–Pratt), Boyer-Moore, and Rabin-Karp. Of these, Rabin-Karp is by far the simplest to understand and implement Analysis The time complexity of the KMP algorithm is O(len(s) + len(p)) "linear" in the worst case. The key behind KMP is that it takes advantage of the succesful character checks during an unsuccessful pattern comparison subroutine. We may have a series of many comparisons that succeed and then even if one fails at the end, we should not repeat the comparison work done since we already saw that a series matched. What we will do is very similar to the naive algorithm, it