Knuth-Morris-Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
CODE ON GITHUB: github.com/neetcode-gh/leetco...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/impleme...
0:00 - Read the problem
1:00 - Review Brute Force O(n * m)
3:45 - Motivation for KMP
5:25 - Understanding LPS
9:15 - Coding LPS
26:35 - Coding KMP
leetcode 28
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#kmp #knuth-morris-pratt #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

Code on Github: github.com/neetcode-gh/leetcode/blob/main/28-Implement-strStr.py I recommend using the timestamps and watching this at 1.5x Speed, at least the LPS portion, which turned out longer than I expected.

[@yotubecreators47]

no that was perfect for guys like me thank you very much

[@ary_21]

Why cant we use in built stl function String.find(substring) To locate the index of string ?

[@xerOnn35]

@@ary_21 because this will only return the first occurence of the substring. Morever, the "substring" function internelly works in O(n) time. So the totall complexity would be O(n^2), where the optimal approch has O(n) time. And that's very bad. And also if you want to count the number of occurences of the substring, the "stl function" approach will definitely give you TLE. :)

[@ary_21]

@@xerOnn35 Got it 👍 Thanks !

[@Luna-vk9xy]

Thank you for acknowledging how complex this algo is. I thought i was crazy for struggling so much. Finally understand it, somewhat :'). Thanks for making this

[@xr_c5516]

exactly. i came back after leaving this algo and did not understand what I wrote at all and I thought I was just being stupid lol

[@thakurritesh19]

If someone says they can explain KMP better, they are lying. It doesn't get any better than what you just did. Amazing Neetcode. 🙏

[@bird5680]

0:35 - Yes, I too would describe independently re-discovering a complex search algorithm during an interview as "very very hard"

[@WoWkiddymage]

lmao, as soon as I submitted his first solution (m * n) doing it myself and it exceeded time I realized this wasn't going to be an "easy" problem :') . WTH is this leetcode.

[@ary_21]

@@WoWkiddymage To be honest trying the same problem with rabin karps algorithm is very easy. If given the hint "each sliding window can have a unique signature" you can yourself re-discover the algo even if not read of before. Kmp , booyre moore , rabin karp are all linear algorithms

[@Iamfafafel]

Especially considering it took 3 guys to initially discover it!

[@theprnvanand]

@@WoWkiddymage well I wrote a brute force (mentioned below, which got accepted btw) but the code was so ugly, I knew for sure there exists an optimal solution and here I am. bool rotateString(string s, string goal) { int n = s.size(); for(int i=0; i

[@aditichourasia2990]

I saw many explanations on kmp algo, but the explanation you provided is the best and the easiest to understand, kudos to you !

[@weihaichen316]

I wish this video came around sooner. Was asked a similar question during a Microsoft interview two weeks ago. The interviewer expected me to come up or remember KMP lol. But thank you NC! Please keep up the good works!

[@zhaovincent8039]

The best online KMP algorithm explanation! Thank you Sir!

[@whiplash1512]

We asked for it in the previous video and you made a video on it, thanks!

[@AsifIqbalR]

Exactly, I literally put a comment on his last video. What a legend

[@gauravgupta5530]

One of the greatest explanations Neel. It's really very helpful and let me tell you I have seen it more than 4 times and now I know how it works. Thanks, man.

[@TheElementFive]

Please try to make future solution videos in this dual screen format. It’s really helpful to visualize the intuition behind each line of code in real time.

[@buggaramvignesh3848]

Yeah

[@brecoldyls]

At 22:00 I think I really started getting it! Thanks Neetcode for the clear explanations as usual.

[@CT-po4xs]

This is the best KMP solution I've been seen, very clear, thank you!

[@yuvrajjoshi4822]

Beautiful explanation, only the one who understands the logic can explain others with such clarity

[@Anirudh-cf3oc]

This is the best explaination video for KMP algorithm!! I find that explaining code parallely is very helpful for this algorithm. Thank you for your efforts!!

[@CEOofTheHood]

Thanks Mr.Neet for listening.

[@adrijachakraborty2316]

This is really a great attempt at trying to explain the KMP and somewhat some intuition behind why it works! Really a very complicated and non-intuitive algorithm but brilliantly explained here.

[@frenzyf3939]

Thank you for your hard work ! Video is incredibly useful and easy to understand.

[@raghavddps2]

This is one of the best explanations to the KMP algorithm, thank you :)

[@yiyunsu7791]

That is super helpful. I finally understand this, two days

[@AsifIqbalR]

Wow. You listened to the feedback from viewers. Goddamn legend ✌

[@tanishqdadhich8589]

Honestly, This was the best explanation I have found on the internet, and trust me I have watched a hell lot smfhhh

[@bharghavak]

It's amazing how stuff like this is actually free. Thanks dude!

[@kamaleshs5324]

This is the first video from NeetCode that I can't seem to understand wow! speaks to the complexity of the algo or maybe I am just mediocre XD

[@nidhiverma1798]

u make it so easy and understandable . ig this is the best video on kmp i came across.

[@XxBruce5002xX]

Excellent attention to feedback

[@mexijie3634]

Best kmp explanation i've ever found on youtube!!!

[@chiragbirla5606]

One of the best explanation out there for this hard hard hard algorithm

[@genghisda236]

Awesome work, ! thank u for putting in so much effort and thanks to me also for making 1/5th effort to make it to the end of this video. good to see that u covered so many test cases, which made the explanation more clear.

[@archivelib3379]

Thank you for this amazing video! Finally, I understood this algorithm.

[@numberonep5404]

Enormous thanks for making this video!

[@harshbhabar51]

Finally understood this KMP in my 6years of studies. Theenks.💪🏼

[@abishekbaiju1705]

Best KMP algo explanation ever. Thanks neetcode.

[@asifiqbalsekh]

You saying again and again it's tough and really it's. But you make the algorithm very easy by your explanation. Superb work....

[@autogenes]

What a great explanation. Thanks!!!!!!

[@SleepeJobs]

Hats off to your effort. 👍🏻

[@yornadnaps4602]

Clean and precise, thanks @NeetCode

[@mygosity]

Thanks NeetCode, it's pretty hard to find a good explanation on the KMP algorithm and you did a great job of explaining it here. Would it be possible for you to cover the Aho Corasick algorithm at some point? I'm finding it difficult to find a good resource explaining that one and having a NeetCode explained version would be a nice follow up to this one as I believe Aho Corasick uses KMP to efficiently find substrings in strings along with Tries.

[@viditvaish7317]

this is the best video on youtube for this question

[@krshivraj10]

Simply beautiful explanation. Very near perfect one.

[@miketsubasa3611]

Very detailed explanation.Thank you very much

[@mhashmi3593]

Great work. Keep it up :-)

[@Mihir.Hundiwala]

Very well explained thank you so much

[@LiXiaoZhi]

Thanks for the amazing explanation!

[@clikiw.8812]

Very helpful, thank you!

[@SoniaStalance]

Tysm! I would have never understood this if I tried learning on my own.

[@spongebobsquarepants4576]

Great explanation! Thank you so much

[@sanatanify03]

best explanation on KMP on yt ❤

[@nehabhavsar4943]

Thanks Man!Saved mine time❤

[@andriidanylov9453]

Appreciate Your hard work. It was hard. I will need to review again a few times to figure out and remember.

[@Pcx357]

Great explanation! 👍

[@aayushranjan3675]

Best explanation! Thanks so much

[@KunalKumar-lb7ir]

Best explaination I found for KMP thanks

[@aadityabisaria5427]

this was so helpful!! thank u!!

[@flocela]

So totally helpful! Thanks!

[@TheLemitek]

Good stuff Sir ☺️

[@user-xc6ez1kj6q]

Awesome explanation!

[@ELMlKO]

why do u sound like you're explaining it to me for the fifth time

[@ameydhimte_c5956]

Yeah true, that's one of your longest videos but you explained KMP-algorithm very clearly

[@nklido]

@NeetCode Please correct me if I'm wrong, but on 19:12, when you say "that's what the 1 tells us..", i think you meant to circle the 1st and the 2nd "A" in the text and not the 1st and 3rd "A".

[@princebillygrahamkarmoker2122]

That just went through my brain. thanks

[@artventure_by_jasse]

Great explanation.

[@rajankhunt7002]

Amazing video and explanation.

[@Luc1an_]

Sir pls take questions from the previous week's contest. They were too odd and problem statement were not put up correctly. Thanks 😊

[@roshangeorge97]

first time in neetcode history* bro made it wild

[@paulofili4486]

Thanks for this

[@danielhemmati]

this was really helpful thanks

[@namankeshari7332]

Loved this video!

[@morningstar1913]

Great Explanation 🙌🙌🙌🙌

[@paraskumar693]

If prevLPS come backs to prevLPS=0 then it can further move max n-i steps ,that's why time complexity is O(N)

[@jinyang4796]

Thank you so much!

[@apputadhiyal9451]

Thank you for the video.

[@satyamgaba]

I was asked this for FAANG interview

[@shiveshgupta1705]

You always explain such this it is one of the best explanation🤩

[@Saeed-Tanjim]

thanks! it's helpful

[@_soundwave_]

I did this yesterday on leetcode. After solving it turnns out to be KMP algorithm.

[@PerryAgent]

Incredible explanation! Thanks for the video.

[@shreyasaini5840]

you are awesome, thank you

[@mandeepsinghsoorma3080]

very helpful video

[@gamefun2525]

Tbh if you wrap your head around the working of the KMP algo, it’s not that complicated and pretty astonishing what it achieves

[@ChoweeChubbs]

thank you sir!

[@user-gh6sz6jn9v]

24:10 I wonder why here we can say LPS[2]'s value means the first two chars match the 5th,6th chars. In my view when the LPS[2] is determined, we don't know the following matches, so its value can only tell the first two match the 1th,2th two (matching prefix-suffix numbers up to current bit). Since then LPS[2] haven't change, why has the meaning changed? Thank you the same.

[@RAjat9590]

The problem with this explanation is while building the needle array, when we have needle[i] == needle[prevLPS], we set the value, lps[i] = prevLPS + 1 but you keep saying we are incrementing the value by 1 of prevLPS index value in lps array whereas we are setting the incremented value of prevLPS and not the index value of it i.e. lps[i] = prevLPS + 1 and NOT lps[i] = lps[prevLPS] + 1 Coincidentally the examples choosen had the same index value and the value inside lps array i.e. value at index 1 is 1 and value at index 2 is 2 that's why i think the choice of example was poor. Other than that the explanation was great.

[@khushwindersingh2541]

I am thinking same, and spent so much time on it tow find out explanation is wrong

[@DeGoya]

Could you also cover Rabin Karp's algorithm for the same leetcode problem?

[@ankitaverma5542]

prevlps is the value stored or the pointer to that location?

[@gothien205]

I do not understand the tricky part when building the LPS array, when i and j do not match, why move j by the VPS[i - 1]? Because move that way you will skip some middle elements. Is there a proof that garentee the longest prefix suffix?

[@kirtikhohal5025]

yew, i also want answer for this logic

[@bhavyagupta3565]

hey Neetcode at timestamp 22:40, why was LPS[6]!= 6? because for the substring 'AAACAAA' -> prefix(AAACAA)==suffix('AAACAA') and that length is 6. please tell me if i am mistaken.

[@shivamkansagara4929]

thank you very much

[@a.m.4154]

If you think KMP is complicated, try Boyer-Moore using both shift-value table and good-suffix rule.

[@genghisda236]

bro i got google screening interview in few days - i remember u said in one of the videos that you can find the screening question online, but i dont see it. although i have prepared from leetcode. But i remember u said the question are easy, it not that easy also, its all good medium level problems

[@Akmabedinkadersafi-O]

Best explanation

[@shreyrawat7108]

Thanks a lot.

[@source144]

Not me legitimately saying "wow" when you went dual screen mode 😭

[@itspete2444]

KMP is great for falling asleep to

[@orellavie6233]

By the end of the video it looks like if you saved the X, the pointer of the needle would need to go back again. If I am not wrong, worst case is O(n*m) like rabin karp, as if the needle is AAAA and the hays is like AAAX copied many many times, it always will go back to the start of LPS array. Thus, O(n*m)

[@supremoluminary]

＠23:34 “C“ is at index three, not index four; 0, 1, 2, 3…

[@ivanzhovannik5419]

Now I finally understood why all my Computer Science peers in uni always told me "Knuth's algos are pure SUFFERING" XD Thanks for this very nice explanation, man! Like :+1:

[@notjustanengineeroffical8084]

It is really good🎉

[@chaithanyachallapalli8608]

cant we use rabin karp algorithm it also takes o(|n| +|m|) right?

[@stat_life]

I love the audacity of Leetcode to post this question as "EASY"

[@sllakshancc]

thank a lot