Table of Contents: (I'm literally screaming. I'm sorry. I want to redo this video to make it better.) Introducing The Creators The KMP Algorithm* 0:00 - 0:15 Problem Introduction With The Naive Approach 0:15 - 2:30 Why The Naive Approach Is Not Good 2:30 - 2:45 Walkthrough How The Algorithm Works 2:45 - 8:14 Building The Suffix-Proper-Prefix Table 8:14 - 12:34 Using The Suffix-Proper-Prefix Table In Traversal Walkthrough 12:34 - 15:08 Time & Space For The Table Build Step 15:08 - 15:51 Time & Space For The Traversal Step 15:51 - 16:08 Overall Time & Space 16:08 - 16:25 Summarizing Our Learnings 16:25 - 16:40 Wrap Up (Begging For More Subs) 16:40 - 17:05 *All 3 of the creators published the final paper together.

@iamjimfan

3 жыл бұрын

That's good enough, I was looking for info on distributed substring searching of very large string. It gives me nice refresh on the basics.

@BackToBackSWE

3 жыл бұрын

great

@piyushyadav9006

3 жыл бұрын

11:50 was the tricky part as we use KMP logic again in building the table itself.

@utkarshbhatnagar768

2 жыл бұрын

it is the best explanation I found on youtube of KMP algo, no need to redo it

@jaivignesh2302

2 жыл бұрын

Hey ., this is great ,,, greater than geeks for geeks really !!!

An algorithm invented by 3 people and they expect us to come up with this in 45 min. Makes sense

@salmanbehen4384

3 жыл бұрын

Fun fact: Dijkstra came up with his algorithm within 20 minutes while having a walk.

@_rmw

3 жыл бұрын

Leetcode "easy"

@StudyWithRishiP

3 жыл бұрын

@@salmanbehen4384 Fun Fact : Dijkastra was thinking about this for a long time.

@user-oy4kf5wr8l

3 жыл бұрын

those algo interview questions are the most meaningless things ever.. system design is kind of interesting...but algo..jesus

@coolmangame4141

3 жыл бұрын

well its popular so its good to know it

BRO STOP YELLING AT ME I ALREADY SUBBED I KNOW YOU'RE GOOD

@BackToBackSWE

5 жыл бұрын

hahaha ok

@dimejifaluyi1759

5 жыл бұрын

Back To Back SWE jk😂 thanks for the vids

@BackToBackSWE

5 жыл бұрын

@@dimejifaluyi1759 yw fam

@eugeneshcherbo9821

4 жыл бұрын

😃

@nataliagrybovska5702

4 жыл бұрын

paused to find this comment

You're the best explainer of algorithms I've ever seen. The extra very visible colored text on the screen while you're explaining also makes a huge difference.

I never knew I needed this kind of teaching which makes me feel like im scolded in order to understand why a box is incremented.

@BackToBackSWE

4 жыл бұрын

lmao, sorry, old video, forgive me

@kiranteja6392

3 жыл бұрын

@@BackToBackSWE Thats actually helped me to understand easily.Best way to teach is to stress key point to understand that concept

Thanks to you I'm one less algoritm away towards achieving my dream. So thanks for the good work and keep it up ;))

@BackToBackSWE

4 жыл бұрын

Yuh. Go achieve them dreams.

I had a hard time understanding KMP but you broke it down so well and I get it now. This goes for all the videos I've watch from you, thank you!

@BackToBackSWE

4 жыл бұрын

nice

The only one to explain the "THE TRICKY PART WHICH SO MANY OTHERS SO CONVENIENTLY SKIP"

@BackToBackSWE

4 жыл бұрын

ok

I trust This dude's Teaching skills with my career, He's so CLEAR, To the Point and explains in Simple Language that no KZread Channel Does that. Absolutely Loved it.

Your explanations are amazing! This is the first time I fully understand the kmp algorithm. Thanks a lot! Keep up the good work ;)

@BackToBackSWE

4 жыл бұрын

thanks and ok.

Calm down a bit you good.

@BackToBackSWE

5 жыл бұрын

hahahahahahahaha, thanks

@peeyar2000

5 жыл бұрын

@@BackToBackSWE ...Yes.. please slow down.. That will help the audience to process what you are saying.

@BackToBackSWE

5 жыл бұрын

@@peeyar2000 ok

@jonathanfoster5106

4 жыл бұрын

@@BackToBackSWE 100% disagree with this comment. your cadence and charisma is half the reason this is all working so well. currently watching through EVERY video on this channel. It's literally the best resource I've ever found on this stuff.

@BackToBackSWE

4 жыл бұрын

@@jonathanfoster5106 hahahahaha ay, wassup, local to this topic they are right and their comments are attesting to the explanation's weakness and incomplete nature. Globally what you observe are correct.

Thank you from my heart. I was about to give up on this algorithm, until I found this video, I appreciate this work so much.

I'm doing leetcode looking for jobs right now, and this was really helpful! I actually understood how the algorithm works for once, instead of the video just showing the algorithm working. Thanks!

Thanks, man! This is the Best ever explanation on KZread. I was stuck on this algorithm for hours

thank you for this content, it helped me a ton!! I loved how hyped you were explaining this algorithm, great job!

Now that's a cool explanation of a seemingly difficult concept. The thing is you cannot watch this video without some sort of preparation. You have to understand the limitations of the naive approach and then think of a logical method/alternative to overcome that. Only after that, when you watch the video and implement the algo, would it become clear to you... Good job with the video, guys!!

@BackToBackSWE

4 жыл бұрын

yeah, this video is ok

I really like your passion and felt very involved during the video So far it’s the most approachable KMP video I’ve seen. I vote for keeping the speed and voice as is, they allow the video to stand out in a good way

@BackToBackSWE

4 жыл бұрын

ye

I love the way you reply literally every single comment in this channel, this shows how much you like what you're doing. And indeed we can see it in your eyes while explaining! Thanks so much for bringing content with such quality and love! I don't usually write comments on KZread but this channel made me stop for some few minutes to write this.

@BackToBackSWE

4 жыл бұрын

I don't like what I'm doing, 70% of the time I hate it. I am just dedicated to whatever I start, it must end successfully at any cost.

@LennethValky19

4 жыл бұрын

@@BackToBackSWE Hahaha really you don't like it? I was 100% sure you loved it because you put so much energy into explaining the algorithms to us. I guess I was wrong then...

people commenting "stop yelling" and all I see is the passion with which you are trying to teach us in the simplest way possible. I came here after watching 2-3 vids but your video cleared all my doubts. Thank you for making this video.

Good lord glad I found you! This is the best explanation I've found! Thank you! Will be following. Don't slow down your enthusiasm makes it fun.

@BackToBackSWE

4 жыл бұрын

ye lol

After reading a bit on Internet and then coming to your video. I got it straight into my head. Really well explained but people really need to have some background before watching such algorithms to just grasp it at one go. Thanks man

@BackToBackSWE

4 жыл бұрын

Oh yeah, this video is old and made in an "ok" fashion

Wow, I applaud your dedication to try and reply to all the comments mate! Good stuff and honestly I should've discovered this channel before!

@BackToBackSWE

3 жыл бұрын

hey

This is the first time I understood KMP algorithm. Thanks a lot!

@BackToBackSWE

4 жыл бұрын

nice

Dude, thanks. That's the most elaborative explanation I came across. Good work!

@BackToBackSWE

4 жыл бұрын

ye

This is amazing. SO clear. Explain every single part of it.

@BackToBackSWE

4 жыл бұрын

great

Like your style of explaining. One of the videos that kept my attention through the end and not bore me to lose focus. Thanks!!

@BackToBackSWE

4 жыл бұрын

great and sure

Man you are great, all your explanations are deep and clear, thanks for your videos 🙌🙌

Greatly explained, i saw a couple other videos but yours made me really understand it

Amazing content. I've been going through your videos and they are so helpful!

Finally, I understand this one! Thank you, you're a hero.

I got confused on the topic quite a bit, but this video explains it real clearly, thanks man, this is greatly appreciated

@BackToBackSWE

4 жыл бұрын

this video is ok

Amazing Amazing explanation buddy! Could not find many on KZread explaining as clearly. Thanks.

@BackToBackSWE

3 жыл бұрын

sure

This is the "BEST" explanation of KMP that ever existed!

Great Video,KMP is now crystal clear to me .Thanks !!! Love from India♥

after lots of videos about Knuth-Morris-Pratt algorithm i just understood how it works...when we have dismatch we just go one step behind and we look at the value of that step and thats it!this is where the i goes(index)..pfff at last!THANKSSSSSSS.LOVE YOU BOY

@BackToBackSWE

2 жыл бұрын

hahaha! try this 5 day free mini course for some good content backtobackswe.com/

@bryanparis7779

2 жыл бұрын

@@BackToBackSWE im on my way to this...many thanks from a Greek postgraduate in Maths and Statistics.

Awesome explanation! Don't worry, the way you're explaining is not screaming. It is rather the enthusiasm with which you explain a problem and I have seen that enthusiasm in almost every video of yours. Looking forward to more of your explanations. Kudos to you!

@BackToBackSWE

3 жыл бұрын

thanks

Whenever I don't understand an algorithm, I come to this page. Dude shout at me like my high school track and field coach, but it definitely gets in my head

@BackToBackSWE

3 жыл бұрын

great to hear - hahahaha, fuck interviews I hate this. No one was going to go and do this and teach in an academic manner that makes sense. We still haven't lived up to the mission/vision I set out with...it's why I get mad...99% of those who understand something won't go teach it, let alone give up their free time and do it for the internet and teach it well. rant

Having an example and working through it step by step is very helpful

Finally got something worth watching... thanks buddy

@BackToBackSWE

5 жыл бұрын

hahahahaha ok, thx, I want to redo this but yeah

Hey dude, thanks for the great vids. I do not know how and why, but somehow your logical explanation of the stuff just rocks compared to many many others. Pls keep doing the good stuff, bro.

@BackToBackSWE

3 жыл бұрын

cuz im average intellect and decided to do all this

The best explanation all over the internet. Hats off to you sir!

@BackToBackSWE

3 жыл бұрын

sure

Honestly..This is the best explanation out there on youtube....Thanks:)

@BackToBackSWE

3 жыл бұрын

eh

Really a superb explanation underlined and outlined all components of the algorithm in a very strategic way. The best thing about your videos is the energy you impart over the explanations about the tricky part or sth unintuitive. Thanks.

@BackToBackSWE

4 жыл бұрын

thx

Didn't understand this during college... but you sir made me understand this within minutes... Great explanation :)

@BackToBackSWE

3 жыл бұрын

great

Great video! Very well explained, as usual. Thank you.

@BackToBackSWE

5 жыл бұрын

haha this vid is decent..old thought too...I wanted to redo it but I never did

I like how you personally react to almost all comments. Keep up the good work bro :)

Finally got it!!! Thank you so much!!

Thank you so much for this! Great video!

Very nice video! it's also interesting to know that we can consider the time complexity as O(n), because if we add an early exit condition for when p is longer than s (where we directly return -1), then we can affirm that m cannot be greater than n, so in the worst case, m would be equal to n, which gives 2n, and by removing the constant, we get a time complexity of O(n)

@BackToBackSWE

3 жыл бұрын

ye

You've got the gift of explaining the concept

Yay I think I understand it at last, thanks man!

Thanks bro best explanation available on internet

if there is any topic i am searching on utube nd u have a video on it. i just simply watch it first, and then continue my research(that most of the time is not even needed, as u clear all the related concepts). thanks

This was awesome man! Finally I understood the algo!

You are very confident and good explanation, thanks!

@BackToBackSWE

3 жыл бұрын

Thank you!

Thanks man, very good explanation!

best Explanation so far on Internet

@BackToBackSWE

4 жыл бұрын

ye

Finally .... best video to undersand kmp algo clearly

@BackToBackSWE

4 жыл бұрын

thanks - the video is decent

Watched several KMP videos and it is the first one that made me understand

@BackToBackSWE

3 жыл бұрын

great

Best explanation for this question is here! Kudos!

You are becoming my first choice for learning any new algorithm. Keep uploading👍 Hats off👏

@BackToBackSWE

2 жыл бұрын

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

Awesome! What a concise explanation.

@BackToBackSWE

5 жыл бұрын

Thanks

I love his energy. Hard to loose focus.

@BackToBackSWE

Жыл бұрын

Happy Holidays! Really glad to help 🎉 Do you know about the 5 Day Free Mini Course? Check it out here - backtobackswe.com/

Perfect explanation. Thank you so much!

@BackToBackSWE

2 жыл бұрын

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

Brilliant explanation - certainly one of the best for the KMP algorithm. I like how you focus on the intuition behind the algorithm, as opposed to the traditional textbook approach. Have you considered writing a book on algorithms?

Thanks a lot. Really helped in understanding clearly !

@BackToBackSWE

3 жыл бұрын

sure!

Bro one of the best explanations. I will check all your content. Keep it up

@BackToBackSWE

4 жыл бұрын

great

Goated at explaining advanced algos!

It is very helpful than the other long KMP articles.

@BackToBackSWE

4 жыл бұрын

nice

Really like the way you explained! thanks man!

@BackToBackSWE

4 жыл бұрын

sure

watched at speed 0.75....:)

@B85046

4 жыл бұрын

Same

@BackToBackSWE

4 жыл бұрын

@@B85046 😭

just amazing explanation bro!

it was a great help. Thanks man

Excellent explanation!

This is the underrated youtube channel on programming

@BackToBackSWE

4 жыл бұрын

nah we are just "rated"

Your explanation is the best among many KZreadrs.

@BackToBackSWE

3 жыл бұрын

thx

Love your channel!!

@BackToBackSWE

4 жыл бұрын

thanks

Your explanations are *dope*

@BackToBackSWE

4 жыл бұрын

thx.

you explained it so nicely

It would really be helpful if you also make videos on some mathematical topics like Number Theory, Combinatorics, Modular Arithmetics, and whichever are important for competitive programming. There are very limited videos on the internet available on these topics and most of them are not well explained. Thanking you in advance 💙

@BackToBackSWE

4 жыл бұрын

I would but our focus is on interviews and helping people around that vs competitive programming. I would but we have to pursue our core mission.

Congratulations, awesome explanation!

@BackToBackSWE

5 жыл бұрын

thanks :)

OMG, this video is soooo great!!! love it

Thank your for making KMP really clear

@BackToBackSWE

3 жыл бұрын

sure

you always make me understand even the hardest algorithm

@BackToBackSWE

4 жыл бұрын

ye

Your video is great! Thank you.

@BackToBackSWE

4 жыл бұрын

thx

i feel yours channel vedios have one solid content for every topic i search every doubt is getting cleared one single veido ..wow thank u soo much bro

@BackToBackSWE

4 жыл бұрын

yes and great.

Very good explanation, you didn't miss any detail of the Algorithm thats what I liked.

@BackToBackSWE

4 жыл бұрын

ye

Thank you so much such a crystal clear explanation with example..

@BackToBackSWE

4 жыл бұрын

sure

❤Thank you so much❤GOD bless you and your family❤

best explanation! Loved it!

@BackToBackSWE

3 жыл бұрын

thx

keep the same pace and enthu..ur making life simple..keep up the way ur doing it...

Nice explanation but I just realized I was holding my breath while watching this video. Just calm down a bit man.

@BackToBackSWE

5 жыл бұрын

hahahahaha, I know: backtobackswe.com/im-sorry

It would be nice to elaborate at 11:55 why "i" becomes the value of P[i-1] and not rolls all the way to zero.

@arnabpoddar6236

3 жыл бұрын

It is a little tricky but I will try, we want to minimize the number of times we roll back to 0. So if there is a miss match,we check if we there is a suffix which is also a prefix in the string we have checked till now, if it is there then we make value of i point at the end of the suffix, which is stored in P[i-1] And if it is not there we directly make i=0. Hope that helps :)

Good video!! Look a few other before this one. This is the first one make me understand.

@BackToBackSWE

4 жыл бұрын

great

Well explained, thanks

@BackToBackSWE

3 жыл бұрын

sure

thank a lot! great explanation bro!

Was really having trouble understanding this algo..This helped a lot :-)

@BackToBackSWE

3 жыл бұрын

great

thank u for the explanation.

Great Explanation, thanks!

@BackToBackSWE

4 жыл бұрын

thx

Great explanation, thank you!

@BackToBackSWE

3 жыл бұрын

sure