Knuth-Morris-Pratt KMP String Matching Algorithm | Search Pattern | GFG POTD

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

[@wearevacationuncoverers]

You deserve more subscribers. Thank you for this masterpiece.

[@codestorywithMIK]

Means a lot. Thank you for your kind words 🙏🙏❤️❤️

[@akhandjeet6114]

bhai meri tarf s bhi 100 rs kr dee

[@thekindspill]

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.

[@shashankvashishtha4454]

i dont think so i dont understand watched this vdo for 3 hours+ still struggling to understand

[@DevOpskagyaan]

“Dry Run is one of the most underrated skills” --- MIK 🔥

[@DevOpskagyaan]

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 🙏🏻🙏🏻

[@RajSingh-te1uo]

1 hour on KMP 😲Thank you so much sir!

[@codestorywithMIK]

Thank you 😇🙏❤️

[@shashankvashishtha4454]

it was three hours for me (watched video parts multiple times) and still i dont understand.

[@insidious_681]

True​@@shashankvashishtha4454

[@aws_handles]

Wo MIK hai, kuch bhi kar sakta hai 🔥🔥 I have no words ❤️🙏🏻

[@souravjoshi2293]

"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.

[@vanshbaghel5884]

Such a huge difference with your explanation vs other explanations. Loving the channel, thanks for everything!!

[@codestorywithMIK]

Thank you so much 🙏😇

[@salmankhader1258]

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.

[@codestorywithMIK]

❤️❤️🙏🙏

[@djhimss4046]

Thankyou so much sir itna achha samjhane ke liye

[@ugcwithaddi]

🔥🔥🙏🏻 Kisi bhi algorithm ka intuition isi channel par mil sakta hai. Salute to your skill 🫡

[@SarthakKumar]

legendary explanation of KMP, after procrastinating for many days finally saw it completely! Great work!

[@codestorywithMIK]

Glad it helped! ❤️❤️🙏🙏

[@brokegod5871]

I solved leetcode hard 1392 Longest Happy Prefix after understanding from this video, thank you

[@amannegi6130]

best vedio on KMP👍

[@codestorywithMIK]

Means a lot to me ❤️🙏🙏🙏

[@insertname6]

Never seen such quality videos on any other channel.

[@abhishekshimpi214]

Completely worth it to watch 1 Hour of video😇. I got a full in-depth understanding of KMP and all its edge cases. Thank You So Much MIK for such amazing content 🤟✌🙏

[@prernagupta7729]

Best video for KMP on youtube !! Why couldn't youtube just showed me this video in the beginning 😴??

[@codestorywithMIK]

Means a lot 🙏🙏

[@rajatjaswaldev]

You wouldn't not understand clearly if youtube would have shown you this video first, it is only because you understood clearly because you had the insight of the algorithm earlier from other videos you had watched. For the first timer the explanation is a bit confusing between length and LPS of length.

[@anshtanwar1813]

Really great, worth spending an hour

[@codestorywithMIK]

Glad you enjoyed it ❤️🙏

[@tarunsingh2480]

Great Explanation Sir. You nailed this algorithm❤❤❤. Never ever will forget this algorithm.

[@ManishKumar-zb2qx]

UnderRated channel

[@KunalSingh-kn2ij]

YOU ARE GREAT SIR JI!!🫡

[@AmanKumar-fy3ym]

very good video, simple and good way of teaching.

[@EB-ot8uu]

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

[@gui-codes]

one of the best explanations for KMP

[@S3aw0lf]

Was wondering when will u upload this cause had to go thru sm vids to understand KMP but coding it is actually hard

[@codestorywithMIK]

Totally agree. Understanding KMP is easy. But the toughest part is - Understanding WHY - coding it up I hope my video helps 🙏🙏❤️❤️

[@nobbiesid1324]

Thanku sir You are my favourite teacher ❤

[@shreyanshjain1595]

VERY WELL EXPLAINED BRO❣

[@Pratham_jaiswal]

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 ✅

[@codestorywithMIK]

Awesome So happy to see this comment ❤️❤️❤️🙏🙏🙏

[@Shivanai_h]

Best explanation on KMP Algo on KZbin. Thanks, MIK:)

[@codestorywithMIK]

Means a lot to me. Thank you so much 🙏😇

[@Ramneet04]

It was the most needed video on KZbin. Thankyou so much ❤❤

[@codestorywithMIK]

My pleasure 😊

[@Ramneet04]

@@codestorywithMIK bhaiya can we do length-- instead of length=lps[length-1]???

[@madugulajoshi5050]

Was waiting for this video. Finally dropped. Thank u bro

[@codestorywithMIK]

Thank you 😇🙏❤️

[@ankitnainwal9714]

Best video on KMP Algorithm 🙌🙌

[@codestorywithMIK]

Means a lot 🙏

[@knowsbetter4113]

❤ crystal clear

[@rugung1381]

what a great explanation bhaiya

[@codestorywithMIK]

❤️🙏😇

[@rugung1381]

aise proper explanation with step by step intuition bohut kaam milta hai@@codestorywithMIK

[@arkojeetbera8584]

Legendary explanation 🔥

[@gauravbanerjee2898]

Thanks a lot for your efforts bhaiya ❤

[@IshaanJoshi-ms9mb]

every second invested was worth it! thanks for helping us out MIK!

[@sahilanand30]

Nicely explained

[@AkshayParihar-n9o]

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.

[@shivanandareddy7067]

I had the same doubt. Take a look at this for "aaa", first two characters (aa) = last two characters but for "aacaa", first three characters (aac) != last three characters (caa)

[@SouvikAdh]

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.

[@vivek3247]

Sir please came up with all algorithm playlist in one place I am waiting

[@monikavaid5083]

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!!!! ☺

[@codestorywithMIK]

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 🙏😇

[@monikavaid5083]

Thanks a lot! 😊😊

[@HimanshuVarshney-z7e]

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 ...

[@codestorywithMIK]

So glad to hear ❤️🙏

[@playwithlinux]

Very nice explanation and intuition broh.... You nailed it. 💛

[@Mohit_Q]

Waiting for more string algorithm

[@MohammedHasmi577]

Sir my dream is to meet you one day u r just ❤🎉

[@tarunpatel1457]

sir please upload the video of Z algorithm and rabin karp. Because no one in youtube teach like you. Please upload these 2 videos on priority if possible. Thank you for all the videos.

[@ss8273]

most most awaited viedo bhaiya, it would be so so great if you make video on segment trees.

[@JagannathDebGunin]

Waiting for KMP Algorithm dada... Thanks a lot...

[@codestorywithMIK]

Thank you 😇🙏❤️

[@xiaoshen194]

Tysm. I have always found KMP and Z algo hard. Hopefully u would cover z algo next. Thnx

[@codestorywithMIK]

Sure I will 😇❤️🙏

[@ChiragWadwa]

what is z algo?

[@chiragsingh8323]

Thanks a lot MIK bhai❤

[@PramodKumar-bu2uf]

thankyou very much Sir 🙂

[@prajwalshaw9217]

Hello sir. Please do make a video on z-algorithm. Your explanations are always the best. Thank u.

[@alfansejigar3636]

you are a very good tutor💓💓

[@harchitgulati3065]

what an explanation man !

[@umeshbisht1054]

Thanku so much bhaiya ❤

[@Lakshya-f4l]

Thankyou so much sir!

[@Ares-go9hd]

Please continue this series

[@nani17290]

MIK! It's a right number

[@rohitrajput2097]

Kudos to your Hard Work Man

[@abhinavnarang4369]

correction at 37:21 it will be kaash 3 length ka suffix and prefix hota, btw ove your content, top notch

[@codestorywithMIK]

❤️❤️❤️

[@UECAbhishekKumar]

Best explanation ❤

[@codestorywithMIK]

Thanks a lot 😊

[@apurav363]

Very helpful

[@39_jatinjain4]

Superb Explanation 🙂🙂

[@codestorywithMIK]

Thank you 🙂

[@Neha_Yadav262]

Explained very well. Can you please upload other string algorithms also.

[@naveroo11]

Very Good Explanation

[@suyashjain3223]

Amazing Explanation!!!🔥🔥

[@ChiragWadwa]

I was waiting for this!❤

[@codestorywithMIK]

Thank you 😇🙏❤️

[@CaptainCoder1]

Good explanation mik thanks a lot❤❤❤❤❤

[@factinsaan4333]

Mik>>striver

[@souravjoshi2293]

I think both are equally good. But Hard problems me mik sir ko beat nahi kar sakta koi explanation.

[@ujwalbarodia4313]

Time complexity of brute force will be O(n^2 * m)

[@jr.stark07]

Bhaiya, rolling hashing + rabin karp algorithm k uper thi ek vdo banado ! ♥️

[@vision7673]

KMP DONE🎉

[@Strawcontamination]

Thank you bhaiya

[@BholaSingh-m8z]

Superb bro excellent content, no doubt this one is the best among all.

[@codestorywithMIK]

Thank you so much 🙂🙏❤️

[@BholaSingh-m8z]

@@codestorywithMIK Boyer Moore Algorithm please

[@-prachi_pandey..]

Explanation ❤

[@siddharth.chandani]

38:16 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 Ips[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,j-1,i-2) are equal to the first three characters from O 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.

[@codestorywithMIK]

Yes yes. Correct ❤️

[@siddharth.chandani]

@codestorywithMIK Always love your videos and this loving nature ❤️

[@codestorywithMIK]

Thank you Sid ❤️🙏 Means a lot

[@santoshpathak8201]

Thank-You so Much Brother .

[@michaelmaahi7384]

Great bhai

[@codestorywithMIK]

Thank you 😇🙏❤️

[@codeandtalk6]

❤❤❤❤

[@phoddaal7130]

kmp itna dhakad samjhaya hai sir (as always), to lage haath Rabin Karp bhi Samjha dijiye 😁😁

[@thaman701]

great sir

[@siddharth.chandani]

38:16 Why not Length = Length - 1 ? Why length is updated with value of lps[length -1] ???

[@siddharth.chandani]

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 Ips[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,j-1,i-2) are equal to the first three characters from O 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. Thanks to @shivamjha1238 's comment!

[@harjotanand834]

One small doubt ....why we're doing lps[len-1] in LPS code ...like from dry run i got to know that its working ....but why not lps[i-1] and why lps[len-1] ?? Please help 🫡

[@subhajitdey135]

I guess i-- can also be done for i and i+1 the LPS can differ maximum by 1. So it doesn't matter. But then we have to initialise another variable for i. Not sure if this explanation is correct or not

[@siddharth.chandani]

Bro why we cannot just simply do length=length -1; as we want to check for shorter lps ??

[@lalithsharma2259]

Self note Why pattern[i]=pattern[len] while Finding LPS Dry run time stap 34:00-36:10

[@anushkathakur6531]

really loved it😍

[@lofireverbz-wy7go]

bhaiya please ek video rabin karp par bi bnado , usske 3-4 hard questions ek jaise hai

[@codestorywithMIK]

In my plan. Soon ❤️🙏

[@atifakhtar8828]

#GODOFDSAMIK

[@maheshkeshwala62]

love you bro

[@a3rdtierguy864]

Bhaiya please make video on rabins carp algo

[@wipeesports8990]

Hello bhaiya, please make 1 or 2 long video on recursion and backtracking please. By explaining from 0 to intermediate level. Please 🙏🏻🙏🏻

[@alfansejigar3636]

can you make a video on leetcode 214. (Shortest Palindrome)

[@Mohit_Q]

Thank you so much ❤

[@atheisth2373]

very nice

[@krishnaramtripathi958]

Thank you!!

[@cosmos1749]

Please explain Rabin karp algo also it will be good in continuation to KMP algo

[@tutuimam3381]

Thankyou 👍🎆

[@omgupta7712]

sir ❤❤❤❤

[@codestorywithMIK]

Thank you 😇🙏❤️

[@namanpadiyar09]

thanks

[@Simar7Singh]

thanx for the video

[@codestorywithMIK]

Thank you so much for watching 🙏