Knuth-Morris-Pratt (KMP) Pattern Matching Substring Search - First Occurrence Of Substring

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given a string s and a pattern p, determine if the pattern exists in the string. Return the index of where the first occurrence starts.
Further Explanation From Tuschar Roy: • Knuth-Morris-Pratt(KMP...
The Brute Force
The naive approach to solving this is looking in s for the first character in p.
If a match is found we begin a search from that index, call it i (for intersect).
We compare the 2nd character of p with index i + 1 of s
We compare the 3rd character of p with index i + 2 of s
...and so on until we have matched to all of p without either having overrun s or having found a mismatch between characters being compared.
We can then return i as our answer.
It doesn’t work well in cases where we see many matching characters followed by a mismatching character.
Complexities:
Time: O( len(s) * len(p) )
In a simple worst case we can have
s = "aaaaaab"
p = "aaab"
The problem is that for each first character match we have the potential to naively go into a search on a string that would never yield a correct answer repeatedly.
Other Algorithms
There are three linear time string matching algorithms: KMP (nuth-Morris-Pratt), Boyer-Moore, and Rabin-Karp.
Of these, Rabin-Karp is by far the simplest to understand and implement
Analysis
The time complexity of the KMP algorithm is O(len(s) + len(p)) "linear" in the worst case.
The key behind KMP is that it takes advantage of the succesful character checks during an unsuccessful pattern comparison subroutine.
We may have a series of many comparisons that succeed and then even if one fails at the end, we should not repeat the comparison work done since we already saw that a series matched.
What we will do is very similar to the naive algorithm, it is just that we save comparisons by tracking the longest propert prefixes of pattern that are also suffixes.
The key is that everytime we have a mismatch we try our best to prevent going backwards in s and repeating comparisons.
Algorithm Steps
We will preprocess the pattern string and create an array that indicates the longest proper prefix which is also suffix at each point in the pattern string.
A proper prefix does not include the original string.
For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. Proper prefixes are “”, “A” and “AB”.
For example, suffixes of "ABC" are, "", "C", "BC", and "ABC". Proper prefixes are "", "C", and "BC".
Why do we care about these??
We know all characters behind our mismatch character match.
If we can find the length of the longest prefix that matches a suffix to that point, we can skip len(prefix) comparisons at the beginning.
The key reason we care about the prefix to suffix is because we want to "teleport" back to as early in the string to the point that we still know that there is a match.
Our goal is to minimize going backwards in our search string.
Complexities:
Time: O( len(p) + len(s) )
We spend len(p) time to build the prefix-suffix table and we spend len(s) time for the traversal on average.
Space: O( len(p) )
Our prefix-suffix table is going to be the length of the pattern string.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 7.13 in "Elements of Programming Interviews" by Adnan Aziz (they do Rabin-Karp but same problem, different algorithm)

[@BackToBackSWE]

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]

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]

great

[@piyushyadav9006]

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

[@utkarshbhatnagar768]

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

[@jaivignesh2302]

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

[@ahmedsyed76]

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

[@salmanbehen4384]

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

[@_rmw]

Leetcode "easy"

[@StudyWithRishiP]

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

[@user-oy4kf5wr8l]

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

[@coolmangame4141]

well its popular so its good to know it

[@dimejifaluyi1759]

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

[@BackToBackSWE]

hahaha ok

[@dimejifaluyi1759]

Back To Back SWE jk😂 thanks for the vids

[@BackToBackSWE]

@@dimejifaluyi1759 yw fam

[@eugeneshcherbo9821]

😃

[@nataliagrybovska5702]

paused to find this comment

[@nhk_kakin_futuremvrcreator]

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.

[@shinra9714]

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]

lmao, sorry, old video, forgive me

[@kiranteja6392]

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

[@GPT-X938]

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]

nice

[@lamihh]

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

[@BackToBackSWE]

Yuh. Go achieve them dreams.

[@akaraze749]

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

[@nono-ip2fv]

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]

ye

[@bryanparis7779]

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]

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

[@bryanparis7779]

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

[@rahulsaxena5015]

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]

yeah, this video is ok

[@sanskrititomar183]

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

[@BackToBackSWE]

thanks and ok.

[@anandchowdhury9262]

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

[@BackToBackSWE]

ok

[@tanmaymalhotra4450]

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.

[@pulkitjain9599]

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]

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

[@fredwooten14]

Calm down a bit you good.

[@BackToBackSWE]

hahahahahahahaha, thanks

[@peeyar2000]

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

[@BackToBackSWE]

@@peeyar2000 ok

[@jonathanfoster5106]

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

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

[@khushdevpandit5865]

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

[@anshu7715]

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

[@hussainalramadan7517]

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.

[@ashwinikumar3721]

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

[@BackToBackSWE]

thanks - the video is decent

[@jalanshmunshi7061]

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]

thanks

[@deepakbhoria4172]

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

[@BackToBackSWE]

great

[@LennethValky19]

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 KZbin but this channel made me stop for some few minutes to write this.

[@BackToBackSWE]

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]

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

[@basu.arijit]

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

[@BackToBackSWE]

nice

[@shivamkumarsingh667]

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

[@sergten]

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]

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 :)

[@ShivamShukla-uz9xs]

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]

thx

[@onkarsingh9661]

Thanks bro best explanation available on internet

[@vinnerzucc1154]

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]

hey

[@EdwardLawPhD]

Your explanation is the best among many KZbinrs.

[@BackToBackSWE]

thx

[@nickkiermaier667]

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]

ye lol

[@sarthakbhatia7888]

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

[@BackToBackSWE]

eh

[@theodoraroseti6429]

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

[@kvnr49]

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]

great and sure

[@LN_1214]

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

[@satyadeeproat2012]

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]

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

[@ketan_sahu]

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]

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.

[@KaranDoshicool]

Best video on KMP

[@BackToBackSWE]

thanks

[@StudyWithRishiP]

Non-indians felt you were yelling, I felt exactly like my classroom :) (Sad-Music in background)

[@pratheep4035]

🤣🤣🤣💯

[@vipulkrishna19]

best Explanation so far on Internet

[@BackToBackSWE]

ye

[@sunilsarode4295]

watched at speed 0.75....:)

[@B85046]

Same

[@BackToBackSWE]

@@B85046 😭

[@uHnodnarB]

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!

[@pranjalshrivstava6519]

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

[@TheJackpotgamer]

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

[@BackToBackSWE]

this video is ok

[@Official-tk3nc]

This is the underrated youtube channel on programming

[@BackToBackSWE]

nah we are just "rated"

[@sandyhan4829]

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

[@BackToBackSWE]

great

[@PickleTickle]

I usually watch you at 2x speed but after seeing the comments, I slowed you down back to 1x to see whats up. You talk unbelievably slow in comparison to 2x LOL I have no idea what people are on about. That said, got stuck on this algo in my lectures but this made it crystal clear cheers

[@BackToBackSWE]

Fascinating. Hello.

[@shariqueshahab]

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

[@BackToBackSWE]

ye

[@priyanshusingh2454]

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

[@BackToBackSWE]

sure

[@Prashantkumar-pn6qq]

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

[@BackToBackSWE]

sure

[@TonyGognitti]

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?

[@insidecode]

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]

ye

[@sultanahmed9694]

You are very confident and good explanation, thanks!

[@BackToBackSWE]

Thank you!

[@abdullahalveeimam7262]

I wish you had gone into a bit more details regarding how the complexity is O(m + n). It's not that trivial as you can see that there's a nested loop which is going back and forth in case of both the build table and traversal. I figured it out though. BTW absolutely love your explanations and the energy.

[@BackToBackSWE]

yeah

[@shubhamgarg4237]

Yes , I had a hard time understanding the complexity,

[@dudu2891]

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/

[@chih-yulin4309]

It is very helpful than the other long KMP articles.

[@BackToBackSWE]

nice

[@VishalKumar-kr9me]

Ohhh I didn't know that you were teaching so fast as compared to your latest videos. I think that was excitement😁😁. But you were fantastic same as you are now

[@BackToBackSWE]

Yeah my b, old videos

[@shilinwang2958]

Find the longest suffix which is also the prefix to save us from reverting the searching. Thanks!

[@BackToBackSWE]

yep! try out our 5 day free mini course on our website - backtobackswe.com/

[@arvindg927]

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]

yes and great.

[@HieuNguyen-ty7vw]

Your video is great! Thank you.

[@BackToBackSWE]

thx

[@amanuel2135]

Goated at explaining advanced algos!

[@user-bx9pj9lc4x]

Wonderful explanation!

[@BackToBackSWE]

thanks

[@kodplanet]

What if we never face a suffix == prefix , what is the time complexity in this case? Is KMP still preferable to Rolling-Hash ?

[@mdotub71]

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]

cuz im average intellect and decided to do all this

[@guowanqi9004]

Hey buddy, I still don't get it :(

[@BackToBackSWE]

This video is ok, one of my first ones, I will redo it one day. Can be made much clearer.

[@575saisri4]

watch it again bcz i did and it worked.

[@emeryy9345]

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

[@aanchalsharma5264]

your content is just superb ..u are just amazing

[@BackToBackSWE]

thx

[@teemu828]

No it was the perfect pace! Good way to keep people engaged in the explanation :)

[@BackToBackSWE]

yo

[@boshiij3449]

Why use KMP when you can use RegEx? Is regex not allowed in technical interviews? Otherwise, a great explanation. I'm binge-watching all your videos!

[@BackToBackSWE]

thx and nice

[@VipinKumar-us1sr]

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

[@BackToBackSWE]

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

[@chandra9491]

just did read other comments, saying slow-down, you don't need to slowdown or low your vice....You voice pitch and speed is perfect, which demands audience attention, so your speed and voice pitch is very important! it has energy and vibe bro! keep it up! one request don't cut/cut video just make it continuous, because its like fragments/clusters for brain! kind of distraction!!!

[@BackToBackSWE]

lol thx

[@siddharthbhati5914]

you are great ,you explain like goddddddd

[@BackToBackSWE]

ye

[@olicmoon]

dude you deserve more likes

[@BackToBackSWE]

thanks

[@adityasrivastava7956]

OMG! John Legend is teaching us

[@parikshitr.rajpara5187]

best explanation! Loved it!

[@BackToBackSWE]

thx

[@ruhinapatel6530]

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

[@jintaoguo821]

Thank your for making KMP really clear

[@BackToBackSWE]

sure

[@jugmilic2096]

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

[@chullupa]

Unrelated but Donald Knuth's last name is pronounced like "Ka-Nooth" Great explanation, very clear.

[@BackToBackSWE]

noted, thanks!

[@cristiangomez7807]

Quick thought: what if pattern is abcd. There is no prefix which is also a sufix... then... complexity would still be O(N*M). And for those cases, it'd be much more convenient to use Rabin Karp, am I mistaken? Thank you for your videos. Im preparing for interviews at Facebook, Google and Apple and y sources are you, leetcode , Abdul Bari.

[@BackToBackSWE]

In not sure, I made this video a long time ago

[@pablocom]

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

[@KhanjanShukla]

Thanks a lot. Really helped in understanding clearly !

[@BackToBackSWE]

sure!

[@ghabrielmielli5858]

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

[@arnabmukherjee5840]

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

[@BackToBackSWE]

great

[@arnabsadhucs]

A complex process has been made more complex here.

[@BackToBackSWE]

sorry - early video, I didnt even understand the topic too well.

[@divianshgupta6525]

Great videos/explanations

[@BackToBackSWE]

thanks.

[@robertpearson8546]

So you want to find the location of each proper suffix which is also a prefix of the pattern?

[@eeee8677]

I hope I am never asked this question, great explanation.

[@melihmtl]

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

[@BackToBackSWE]

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

[@NikolozVarazashvili]

Well explained, thanks

[@BackToBackSWE]

sure

[@joshuanorris3776]

Thank you so much for this! Great video!

[@karthiksharma2296]

Was about to kms , this algo was so hard to understand, but man you saved me so much time plus you made me understand it really easily ( I have a caveman brain sorry for No punctuations in the paragraph ⁦:⁠^⁠)⁩ ) Thank you for this vid ❤

[@MrBetaJacques]

this is the funniest contrast ive experienced in a while. Came here because my prof is a asmr-nap-mediation-device, but you... you might be TOO exited. But ive understood it... so thx i guess ?

[@emmanuel5566]

You've got the gift of explaining the concept

[@harshalokavarapu302]

Beats reading the wiki page. Thanks!

[@BackToBackSWE]

ye

[@aj9706]

Understood kmp concept from Ur channel and prefix array building from Tushar Roy channel. Thank u Pls make a video on insert delete getrandom.

[@BackToBackSWE]

ye

[@georgeyarr3475]

Hi, what is the point in making an entry in the border table for the last character in the substring? As there cant be a mismatch that requires its use? Once you get to that point in the substring you'll either find a match and the algorithm terminates, or you find a mismatch and look at the border of the table[0...7]

[@glatavento1513]

best kmp video on ytb

[@farizma]

Woww ❤️ explanation is so amazing, loving ur videos. 💕👍 Thanks for making these valuable videos. ☺️

[@varunrao2135]

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

[@BackToBackSWE]

great