In our quest to cover up all different coding patterns for interviews, we have landed on KMP or Knuth Morris Pratt Algorithm. It is a complicated string matching algorithm to understand but has good application.
Here are a few questions to solve on KMP:
Longest Happy Prefix: leetcode.com/problems/longest...
Shortest Palindrome: leetcode.com/problems/shortes...
With this, we have completed 2 different string matching algos - Z and KMP. We are left with Rabin Karp
Connect on Insta: / bharatkhanna1995
Connect on Linkedin: / bharat-khanna-717b4817b
00:00-5:15 Introduction to KMP and LPS Array
5:16-8:14 Brute Force O(n^3) for LPS Computation
8:14-9:17 Using LPS for String Matching
9:18-12:07 Optimising LPS Computation to O(N) - Upper Bound for lps[I]
12:08-16:06 Optimising LPS Computation to O(N) - Using Past lps values
16:07-20:14 Pseudo - Code for this optimised code
20:15-23:43 Longest Happy Prefix
23:44-25:50 How is this O(N)?
25:51-26:56 Concluding Remarks