Knuth-Morris-Pratt KMP String Matching Algorithm | Search Pattern | GFG POTD
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- Whatsapp Community Link : www.whatsapp.c...
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"
Share your learnings on LinkedIn, Twitter (X), Instagram, Facebook(Meta) with #codestorywithmik & feel free to tag me.
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) : github.com/MAZ...
Leetcode Link : www.geeksforge...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / 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
You deserve more subscribers. Thank you for this masterpiece.
Means a lot. Thank you for your kind words 🙏🙏❤️❤️
A suggestion to everyone :
1. Those who want a crash course on KMP - Abdul Bari Sir's Video is good
2. Those who want to understand how KMP works and see multiple Dry Runs (Post-mortem of KMP) - Legend MIK is here
Understanding KMP is easy but to understand the code on how to implement was the toughest part and this 1 hour video was worth watching. This is the only channel where I comment whole heartedly because of the quality of the content and this legend's hard work. Hats off king.
i dont think so i dont understand watched this vdo for 3 hours+ still struggling to understand
I think KMP is one of those algorithms jisko samajhna easy hai but code me implement karna very tough. Thanks for explaining code line by line 🙏🏻🙏🏻
“Dry Run is one of the most underrated skills”
--- MIK 🔥
1 hour on KMP 😲Thank you so much sir!
Thank you 😇🙏❤️
it was three hours for me (watched video parts multiple times) and still i dont understand.
True@@shashankvashishtha4454
"History will remember this legendary explanation of KMP."
Just completed the video. I was reading comments of others in this video.
I agree with comments that understanding the concept is easy but being able to code it and explain the intuition and code it up is difficult and you are just marvellous in breaking down a big problem into smaller chunks. And last but not the least, I want this patience level of doing dry runs like you.
Wo MIK hai, kuch bhi kar sakta hai 🔥🔥
I have no words ❤️🙏🏻
I watched so many videos on kmp but every time i forgot the Algorithm. I find this video as one stop solution. The intuition behind using lps is something which we can expect only from this channel. Thanks a lot.
❤️❤️🙏🙏
Such a huge difference with your explanation vs other explanations.
Loving the channel, thanks for everything!!
Thank you so much 🙏😇
Was wondering when will u upload this cause had to go thru sm vids to understand KMP but coding it is actually hard
Totally agree. Understanding KMP is easy. But the toughest part is
- Understanding WHY
- coding it up
I hope my video helps 🙏🙏❤️❤️
🔥🔥🙏🏻
Kisi bhi algorithm ka intuition isi channel par mil sakta hai. Salute to your skill 🫡
Best video for KMP on youtube !!
Why couldn't youtube just showed me this video in the beginning 😴??
Means a lot 🙏🙏
Never seen such quality videos on any other channel.
legendary explanation of KMP, after procrastinating for many days finally saw it completely! Great work!
Glad it helped! ❤️❤️🙏🙏
best vedio on KMP👍
Means a lot to me ❤️🙏🙏🙏
I am sure this is the only best detailed explanation on KMP which details out the implementation also line by line. I don't know who you are , but you are doing an amazing work. Hope to collaborate with you someday
UnderRated channel
Was waiting for this video. Finally dropped. Thank u bro
Thank you 😇🙏❤️
Thanks a lot bro ❤
I watched your video of kmp friday 12. Jan 24 and today 14 jan 24 Leetcode WC has 2 question on kmp.😂
Done both ✅
Awesome
So happy to see this comment ❤️❤️❤️🙏🙏🙏
Mik>>striver
I think both are equally good.
But Hard problems me mik sir ko beat nahi kar sakta koi explanation.
It was the most needed video on TH-cam. Thankyou so much ❤❤
My pleasure 😊
@@codestorywithMIK bhaiya can we do length-- instead of length=lps[length-1]???
every second invested was worth it! thanks for helping us out MIK!
Tysm. I have always found KMP and Z algo hard. Hopefully u would cover z algo next. Thnx
Sure I will 😇❤️🙏
what is z algo?
Really great, worth spending an hour
Glad you enjoyed it ❤️🙏
Best explanation on KMP Algo on TH-cam.
Thanks, MIK:)
Means a lot to me. Thank you so much 🙏😇
Very nice explanation and intuition broh.... You nailed it. 💛
YOU ARE GREAT SIR JI!!🫡
what a great explanation bhaiya
❤️🙏😇
aise proper explanation with step by step intuition bohut kaam milta hai@@codestorywithMIK
Best video on KMP Algorithm 🙌🙌
Means a lot 🙏
Thanku sir
You are my favourite teacher ❤
Thanks a lot for your efforts bhaiya ❤
Video was extremely good. The only thing that could be added was explaining time complexity after using KMP. Thank you so very much for the best explanation on internet!!!! ☺
Thank you so much.
Actually the Time Complexity is O(m+n).
I will ensure I always add TC and SC after explaining.
Thank you 🙏😇
Thanks a lot! 😊😊
most most awaited viedo bhaiya, it would be so so great if you make video on segment trees.
I was waiting for this!❤
Thank you 😇🙏❤️
one of the best explanations for KMP
kmp itna dhakad samjhaya hai sir (as always),
to lage haath Rabin Karp bhi Samjha dijiye 😁😁
Nicely explained
❤ crystal clear
Sir please came up with all algorithm playlist in one place I am waiting
Legendary explanation 🔥
Waiting for more string algorithm
Thanks a lot MIK bhai❤
bhaiya aapki wajah se easy question me atakne wale ne aaj hard question(3036. Number of Subarrays That Match a Pattern II) bna liya ...thanks for everything in coding bhaiya ...please continue this playlist ...
So glad to hear ❤️🙏
Thanks for the video. I finally can understand KMP now. One observation if txt="aaa" and pat="aaaa", your implementation will fail since you didn't add length check of i & j at line no 35 else-if check. Got this test case failure while solving leetcode-28.
Waiting for KMP Algorithm dada...
Thanks a lot...
Thank you 😇🙏❤️
what an explanation man !
you are a very good tutor💓💓
I haven't watch the complete video, just go through the brute force approach that you have mentioned, I will watch the video tomorrow, initially looking at brute force, I think of sliding window, lets say we have pat string of size k, and we have to to find a substring of pat in txt, so cant we simply uses the fixed sized sliding window concept, removing previous occurences and taking advantage of the precomputed results? I might be completely wrong here, feel free to correct me! 🫂❤
Your intuition is correct, and the sliding window technique can indeed be used to efficiently search for a pattern within a text. While the Knuth-Morris-Pratt (KMP) algorithm is specifically designed for pattern matching, the sliding window technique is a general approach that can be applied to various problems, including substring search.
In the context of substring search, the sliding window technique involves maintaining a window of a fixed size as it moves through the text. You compare the contents of the window with the pattern you are searching for and update the window accordingly.
Here's a basic outline of how the sliding window technique could be applied to substring search:
---- Initialize a window of size k at the beginning of the text.
---- Check if the content of the window matches the pattern.
---- If a match is found, you have found the substring.
---- Move the window by one position and repeat steps 2-3 until the end of the text is reached.
However, it's important to note that the sliding window technique may not be as efficient as specialized algorithms like KMP for general pattern matching. The KMP algorithm has been specifically designed to take advantage of the structure of the pattern itself, allowing it to skip unnecessary comparisons and achieve better overall performance in certain scenarios.
In short, while the sliding window technique can be used for substring search, it may not be as optimized as algorithms like KMP for generic pattern matching tasks. The choice of algorithm depends on the specific requirements and characteristics of the problem you are trying to solve.
Self note
Why pattern[i]=pattern[len] while Finding LPS
Dry run time stap 34:00-36:10
One significant Question came to my mind is, 22:00 While calculating LPS[2] we took an A as common, but 24:47 while deriving LPS[6] we did not took C as common even though the length was odd in both the cases.
MIK! It's a right number
thankyou very much Sir 🙂
why lps for one length is 0?
see, we are looking for proper prefix (not just prefix), and proper prefix means the prefix can't be equal to the whole string
so for str = "a", we can't take "a" as a proper prefix, because it's whole string
But, for str = "aaaa", the lps will be of length = 3, because we can take "aaa_" as the proper prefix which is not whole string and take "_aaa" as the suffix.
Perfect 👌👌👌
Hello sir. Please do make a video on z-algorithm. Your explanations are always the best. Thank u.
Superb Explanation 🙂🙂
Thank you 🙂
correction at 37:21 it will be kaash 3 length ka suffix and prefix hota, btw ove your content, top notch
❤️❤️❤️
Good explanation mik thanks a lot❤❤❤❤❤
Superb bro excellent content, no doubt this one is the best among all.
Thank you so much 🙂🙏❤️
@@codestorywithMIK Boyer Moore Algorithm please
Kudos to your Hard Work Man
Sir codeforces k lya v ak playlist banaya please
Let me try to take out some time to explore
Best explanation ❤
Thanks a lot 😊
Great bhai
Thank you 😇🙏❤️
bhaiya please ek video rabin karp par bi bnado , usske 3-4 hard questions ek jaise hai
In my plan. Soon ❤️🙏
Explained very well. Can you please upload other string algorithms also.
Amazing Explanation!!!🔥🔥
32:09 LPS CODE
Bhaiya please make video on rabins carp algo
Bhaiya, rolling hashing + rabin karp algorithm k uper thi ek vdo banado ! ♥️
love you bro
#GODOFDSAMIK
Explanation ❤
thanx for the video
Thank you so much for watching 🙏
Thanku so much bhaiya ❤
which tablet do sir use>???
Very Good Explanation
KMP DONE🎉
great sir
thanks
really loved it😍
sir ❤❤❤❤
Thank you 😇🙏❤️
Sir if possible could you please make a video on Z-function .
Noted
bhaiya, 25:30 time stamp par 6th index mein 4 hona chahiya na?? aaac == caaa
aagya samjh....read one of your replies😂❤
Bhaiya Can you please make video on Rabin Karp and Z algorithm? Pls reply
bhaiya can u tell me on which patterns we should concentrate more
Thank you!!
Thank you bhaiya
Thank-You so Much Brother .
sir make video on Rabin karp algorithm
@codestorywithMIk: How about Manacher's Algorithm in coming video, Question related to it, Longest palindromic substring of LC, that would be great!
Noted ❤️❤️
Please explain Rabin karp algo also it will be good in continuation to KMP algo
very nice
CFBR
please make video on rabin karp also
Thankyou 👍🎆
You should also pin playlist for this series.
brother i am just confused in only one paert that why did you put len = lps[len-1] when there is no match during a lps array
You can do len- - only as well.
It will work the same way.
The motive is to try with shorter length if no match.
@@codestorywithMIK We cannot use len--, we have to do len=lps[len-1].
The logic behind this is that let's say upto some index i, len is 10, that means that prefix of length 10 characters is equal to the suffix (upto i) of 10 characters,
Now let's say at the index 9(i.e length 10) if the lps[9] is let's say 3, that means that the prefix of the length 3 is equal to suffix of length 3 (upto index 9), which in turn would mean that those same three characters will be present in the suffix of length 10 (upto i) as the whole string of length 10 (from 0) is repeated at the end as the suffix till index i , this is the most important part of this logic (remember this)
With all this in mind if we want to find lps[i+1] and s[i+1]!=s[len], since we know that the last three characters(ie. i,i-1,i-2) are equal to the first three characters from 0 and also equal to the last three characters upto index 9 (from the above point marked as remember this),
so if we check at index 3(i.e length 4) and it matches with s[i+1], we can have the lps[i+1]=4.
This will be achieved if we set the len to lps[len-1], i.e set the length to the length of the longest prefix suffix pair, at the index len-1, then apply the basic idea of kmp.
Also with doing len--, with duplicates present we can incorrectly match s[i]=s[len] at some higher len value, where prefix might not be equal to suffix.
Hello bhaiya, please make 1 or 2 long video on recursion and backtracking please. By explaining from 0 to intermediate level. Please 🙏🏻🙏🏻
can you make a video on leetcode 214. (Shortest Palindrome)
bhaiya ek Z Algo pe bhi video bna do please 🙏🙏🙏🙏
Thank you so much ❤