Knuth-Morris-Pratt KMP String Matching Algorithm | Search Pattern | GFG POTD
268Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 1st Video on our playlist "String Algorithms".
In this video we will try to understand a very popular string pattern matching Algorithm - "Knuth-Morris-Pratt KMP String Matching Algorithm"
We will also solve today's GFG POTD using same code of KMP algorithm - "Search Pattern"
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Knuth-Morris-Pratt KMP String Matching Algorithm | Search Pattern
Company Tags : MICROSOFT
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/String%20Algorithms/Knuth-Morris-Pratt%20KMP%20String%20Matching%20Algorithm.cpp
Leetcode Link : https://www.geeksforgeeks.org/problems/search-pattern0205/1
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach Summary : We make use of The Knuth-Morris-Pratt (KMP) algorithm which is an efficient string searching algorithm that precomputes the longest proper prefix which is also a suffix for each prefix of the pattern, stored in an array called LPS. During the search, it uses the LPS array to skip unnecessary character comparisons, resulting in a linear time complexity of O(N + M) for a text of length N and a pattern of length M. KMP is widely used for efficient substring search, particularly in scenarios with large datasets.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear