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

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

Рет қаралды 107,669

Күн бұрын

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

Пікірлер: 159

@NeetCode 2 жыл бұрын

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 2 жыл бұрын

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 2 жыл бұрын

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 2 жыл бұрын

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

@WoWkiddymage 2 жыл бұрын

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 8 ай бұрын

Especially considering it took 3 guys to initially discover it!

@theprnvanand 7 ай бұрын

@@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 2 жыл бұрын

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 2 жыл бұрын

The best online KMP algorithm explanation! Thank you Sir!

@TheElementFive 2 жыл бұрын

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 2 жыл бұрын

Yeah

@gauravgupta5530 2 жыл бұрын

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.

@whiplash1512 2 жыл бұрын

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

@AsifIqbalR 2 жыл бұрын

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

@CT-po4xs Жыл бұрын

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

@frenzyf3939 2 жыл бұрын

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

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

@brecoldyls Жыл бұрын

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

@CEOofTheHood 2 жыл бұрын

Thanks Mr.Neet for listening.

@raghavddps2 Жыл бұрын

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

@yiyunsu7791 2 жыл бұрын

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

@yuvrajjoshi4822 7 ай бұрын

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

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

@nidhiverma1798 Жыл бұрын

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

@genghisda236 9 ай бұрын

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.

@tanishqdadhich8589 2 жыл бұрын

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

@mygosity 2 жыл бұрын

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.

@kamaleshs5324 2 жыл бұрын

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

@bharghavak Жыл бұрын

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

@archivelib3379 Жыл бұрын

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

@AsifIqbalR 2 жыл бұрын

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

@mexijie3634 Жыл бұрын

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

@XxBruce5002xX 2 жыл бұрын

Excellent attention to feedback

@numberonep5404 2 жыл бұрын

Enormous thanks for making this video!

@autogenes 2 жыл бұрын

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

@asifiqbalsekh 2 жыл бұрын

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

@abishekbaiju1705 Жыл бұрын

Best KMP algo explanation ever. Thanks neetcode.

@harshbhabar51 11 ай бұрын

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

@yornadnaps4602 9 ай бұрын

Clean and precise, thanks @NeetCode

@SleepeJobs 2 жыл бұрын

Hats off to your effort. 👍🏻

@Mihir.Hundiwala Жыл бұрын

Very well explained thank you so much

@ELMlKO 6 ай бұрын

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

@clikiw.8812 2 жыл бұрын

Very helpful, thank you!

@miketsubasa3611 6 ай бұрын

Very detailed explanation.Thank you very much

@krshivraj10 8 ай бұрын

Simply beautiful explanation. Very near perfect one.

@mhashmi3593 2 жыл бұрын

Great work. Keep it up :-)

@andriidanylov9453 2 ай бұрын

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

@spongebobsquarepants4576 Ай бұрын

Great explanation! Thank you so much

@viditvaish7317 9 ай бұрын

this is the best video on youtube for this question

@LiXiaoZhi Жыл бұрын

Thanks for the amazing explanation!

@Luc1an_ 2 жыл бұрын

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

@SoniaStalance Жыл бұрын

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

@nehabhavsar4943 Жыл бұрын

Thanks Man!Saved mine time❤

@Pcx357 Жыл бұрын

Great explanation! 👍

@aadityabisaria5427 Жыл бұрын

this was so helpful!! thank u!!

@aayushranjan3675 Жыл бұрын

Best explanation! Thanks so much

@flocela 8 ай бұрын

So totally helpful! Thanks!

@TheLemitek 2 жыл бұрын

Good stuff Sir ☺️

@sanatanify03 9 ай бұрын

best explanation on KMP on yt ❤

@KunalKumar-lb7ir 7 ай бұрын

Best explaination I found for KMP thanks

@paulofili4486 2 жыл бұрын

Thanks for this

@chiragbirla5606 25 күн бұрын

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

@user-xc6ez1kj6q 6 ай бұрын

Awesome explanation!

@ameydhimte_c5956 Жыл бұрын

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

@artventure_by_jasse 2 жыл бұрын

Great explanation.

@DeGoya Жыл бұрын

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

@rajankhunt7002 Жыл бұрын

Amazing video and explanation.

@roshangeorge97 11 ай бұрын

first time in neetcode history* bro made it wild

@nklido 6 ай бұрын

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

@namankeshari7332 Жыл бұрын

Loved this video!

@apputadhiyal9451 2 ай бұрын

Thank you for the video.

@danielhemmati Жыл бұрын

this was really helpful thanks

@morningstar1913 18 күн бұрын

Great Explanation 🙌🙌🙌🙌

@princebillygrahamkarmoker2122 11 ай бұрын

That just went through my brain. thanks

@ankitaverma5542 4 ай бұрын

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

@jinyang4796 2 жыл бұрын

Thank you so much!

@_soundwave_ 11 ай бұрын

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

@J1MKAKA1N Жыл бұрын

Can someone tell the difference between LPS and DFA (Deterministic finite automaton) in the context of the algorithm?

@gothien205 2 жыл бұрын

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 2 жыл бұрын

yew, i also want answer for this logic

@PerryAgent 2 жыл бұрын

Incredible explanation! Thanks for the video.

@genghisda236 8 ай бұрын

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

@chaithanyachallapalli8608 Жыл бұрын

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

@paraskumar693 2 жыл бұрын

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

@shiveshgupta1705 Ай бұрын

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

@satyamgaba Жыл бұрын

I was asked this for FAANG interview

@user-et8om7cl2j Жыл бұрын

I don't understand why we use prevLps as an index , but set the value from lps[prevLps - 1]; Why value can be used as index?

@bhavyagupta3565 3 ай бұрын

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.

@Saeed-Tanjim Жыл бұрын

thanks! it's helpful

@ChoweeChubbs 10 ай бұрын

thank you sir!

@gothien205 2 жыл бұрын

I dont understand why prevLPS = lps[prevLPS - 1]? is that always right?

@shreyasaini5840 6 ай бұрын

you are awesome, thank you

@opus6630 Жыл бұрын

Hey guys, I have a question regarding the calculation of the LPS array. When it comes to the "else" condition, why do we let prevLPS = LPS[prevLPS-1] instead of decrementing prevLPS by 1? 🤔 THANKS.

@prakhargupta4320 11 ай бұрын

I was wondering the same thing If you found an explanation please share

@vijaybenz9741 6 ай бұрын

@@prakhargupta4320 checj for other strings as well youy will get it

@shivamkansagara4929 Жыл бұрын

thank you very much

@mandeepsinghsoorma3080 Жыл бұрын

very helpful video

@user-gh6sz6jn9v 2 ай бұрын

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.

@shreyrawat7108 11 ай бұрын

Thanks a lot.

@shaporovanatalia6805 Жыл бұрын

am I correct that these algorithm does not work correct for such case string haystack ("ababcaababcaabc"); string needle ("ababcaabc");

@orellavie6233 2 жыл бұрын

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)

@MrLeyt1125 4 ай бұрын

Can you do Leetcode 30 video? I wander how can we implement KMP in it

@Akmabedinkadersafi-O 6 ай бұрын

Best explanation

@gamefun2525 3 ай бұрын

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

@source144 2 жыл бұрын

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

@supremoluminary Жыл бұрын

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

@ishanporwal4403 Жыл бұрын

at 24:28 you said that that we would take lps[prevLPS] and add 1 to it but in the code in first condition you wrote lps[i]=prevLPS+1 and not lps[prevLPS] +1