Knuth-Morris-Pratt(KMP) Pattern Matching(Substring search)

[@allupeng1993]

thank u , this is the best kmp-algorithm introduction i have never seen, i love your video. now is 2023, but your video is classic and simple for everyone who want to learn kmp truly!

[@shubhamgoyal7596]

How someone can give such a easy explanation of such a harsh topic...you are awesome sir.

[@tusharroy2525]

thx.

[@aksharmishra9693]

Damm 8y old comment😮 Bhai abhi aap kya krte ho

[@Your_Soul_13]

@@tusharroy2525 sir aap bhi jaat hai kya

[@aliaksandrsheliutsin2374]

I spent 2 hours reading algo book and papers but understand nothing. I watched your video 2 times and understand everything. Thank you very much!

[@d2macster]

this visualization in 5 minutes explained what took me 2 hours reading other sources

[@manasbudam7192]

I think this is the best introduction any one can get for kmp.It will be better understood if you stress the lps array as an automaton which shows the index from which the comparision must continue.Thank you Tushar sir. Once again I want to say that this is the best introduction any one can get for kmp.

[@111rhishishranjan2]

After 7 yrs, what you do now sir??

[@howhello354]

​@111rhishishranjan2 after 7 months, what you do now?

[@shubh13799]

old is gold, now this person is working as a technology lead.

[@BackToBackSWE]

This video is great, really clarifies things.

[@dampdigits]

Beautiful explanation. You address the actual logic of finding the longest suffix that is a prefix in a substring, which it easier to understand.

[@RudolfEremyan]

The Best explanation of KMP in KZbin)) 12 minutes of helpfull information)))

[@sharcodes]

Watching this video on 2023, I can say you are the real gems. You made a video when no was making such good quality content. Thank you 😊.

[@SanaMalik-ss3sh]

very good work. I have seen a lot of videos about this topic but this is best one through which i have completely unterstand this topic........Thank you sir

[@AbhishekSharma20]

I browsed over internet for hours, and still couldn't get such a simple explanation as this. Then I remembered this song: "Jag ghumeya, thare jaisa na koi". Thanks for uploading. You're helping thousands of people.

[@RamendraSinha]

দ্য ঃ ডট t do এত দূর

[@bhavukmathur2709]

Can the fees that I innocently paid to my college lecturers be taken back and given to you..??

[@santuchaitu]

very True. Thank you Tushar for explaining very clearly.

[@vis40sinha]

mathur ji emotional(bhavuk) kar diye

[@johnzhang4353]

i totally agree with you.

[@shubhamgarg4227]

zyada bhavuk ho liye :P

[@tusharroy2525]

I can take the money...:)

[@hillstudios1]

One of the best.Tushur is like a saviour who comes helps humanity and never returns back

[@anuveshkothari]

this video made KMP pattern matching very simple ... all thanks to tushar

[@almamun.]

Number one explanation all of kmp tutorials in utube.

[@ravi-mo6js]

Very good and simple explanation bro.. Ofcourse we INDIANS are legends in these cases..

[@webv2755]

Best video so far I watched for KMP Algorithm, Watching in 2024...

[@plontulublalulu]

You are consistently the best explainer of these concepts. Thank you a ton

[@aj9706]

Explanation for Prefix array building in this video is the best in KZbin.

[@harpercfc_]

I promise you this is the BEST KMP algorithm tutorial around the world. Thanks for your video which made me understand KMP finally. Really really awesome!

[@jatinbalani1349]

Very precise explanation. Examples are used and explained simply.

[@robertpierce5142]

The best explanation of the failure table I've found so far. Thanks!

[@adeypurohit01]

The only place on YT where I understood KMP !! Thanks a lottt Sir 🙏

[@monx]

The first 5 minutes explaining the intuition is time well spent. Thanks Mr. Roy!

[@Alpha-nn8mn]

7 years old video, but still one of the best! Thank You Tushar

[@balajijayasankar4502]

A very simple and clear explanation to a seemingly complicated algorithm. Glad I found this.

[@saurabhprasad4499]

You are a naturally good teacher Tushar

[@mubeenullhaq6429]

Just watched this video 5 hours before the exams .. found it so much easy.. God bless you Sir. Respect from Pakistan...:)

[@shuyao5248]

I couldn't understand this earlier. now I'm very clear about this. Such a awesome explanation. Thankyou very much sir.

[@ajinkya5043]

This was really really helpful...no other video explained KMP algorithm upto this level of clarity...Thanks Tushar Sir!

[@tusharroy2525]

welcome

[@111rhishishranjan2]

what you do now ??

[@mayurbhat6564]

Awesome sir I have never ever understood this kmp in my class as best as u taught.... Congo

[@aditijain515]

Wow....This is the best explaination one can ever get on KMP. Thanks alot :)

[@tusharroy2525]

welcome

[@tusharchamp488]

@@kamalkishor543210 kuch jyada hi hogya ye toh

[@nataliazolotukhina9469]

I've watched lots of videos about KMP but this explanation is the most useful! Thank you!

[@ghostgutarist5234]

Me: I will learn KMP. He: Prefix, Suffix, Suffix, Prefix.... Me: Damn, I am confused... maybe Some other day.

[@sunguru981]

LMAO .. Same here XD

[@akashjain7378]

Check out Abdul Bari's video on the same topic. You will surely understand!

[@gabrieledarrigo310]

lol

[@sarkarsh5537]

@@akashjain7378 More like check Abdul Bari's video, and come back and watch this video, because I think both videos are helpful to get a clear understanding of the entire concept.

[@hagartm]

Some algos you can tackle in one attempt, the others(?) .... you have to grapple with a bit more. :)

[@MatyyRdk]

Hands down best videos on algorithms

[@lolno6527]

Tushar you are doing a superb job buddy! I have stopped going to my lectures. I got a 46/50 watching your videos on my midterm! Thanks mate! With love from Canada!

[@111rhishishranjan2]

what you do now ??

[@AbhayKumar-oz4oh]

you are awesome,after watching this vdo KMP algo is very very very very simple for me Hats off to your teaching style sir

[@malharjajoo7393]

Basically to understand what happens at 9:40 - Useful to understand - Value stored in the array at index "i" - Length of prefix matched ( from the start , hence we do A[i] = j+1 ) upto that index i. "j" index - this is actually the length of the prefix matched from the start. This index keeps on getting reset ( not always to 0 ) . "i" index - this is just iterating through every character of the substring. 1) We increment "i" whenevr there is a mismatch ( A[j] != A[i] ) and j=0 or if there is a match ( A[j]==A[i] ,in which case j++ is also done ) 2) We "reset" "j" whenever there is a mismatch ( A[i] != A[j] ) But how do we reset it ? Key logic - Go to index j-1. look at A[j -1 ] , this gives prefix length matched upto current "i-1". Hence we start checking from A[A[j-1]] against current character at "i". To convince yourself of this , think of "j" and "i" moving together when they match characters.

[@youarecorrectiamwrongbecau1338]

this should be the first/pinned comment

[@ChalanthornC]

THX!

[@braceyourself1097]

bruh

[@chloeyeocodes]

Thank you!!! The explanation at 3:24 was so good! It really helps if you watch this video with the pseudocode for the prefix/lps table and the peusodocde for kmp search in front of you 😄 happy coding!

[@azgddis]

Search logic first Kmp to understand the complete logic. Excellent explanation with code.

[@AnkitSharma13]

Superb explanation. Wow. Had been to so many other channels to understand but in vain. Thanks Tushar.

[@FrostyBaka]

Best explanation of KMP algorithm that i found. Thanks

[@snehallotus]

Superb explanation of failure function with all the scenarios.. and then the actual string matching algo (y)

[@kakyoism]

Great presentation. My first reaction to the algo is "Why must we care about prefix/suffix". I found it difficult to figure out the impact with the first example in the video. Then my take: Say if the input Text was "axax...", the Pattern was "axad...", then the initial matching would fail at the second 'x'. However, then we cannot slide "axa" of Pattern past the second 'x' in Text. We must match Pattern's current prefix, i.e., the 1st 'a', against Text's current suffix, i.e., the 2nd 'a'. This is why we must examine the prefix/suffix situation in the substring before EVERY fail point. Another viewpoint of this problem: Without explicitly backtracking the character at the fail point, we don't know if there could be another occurrence of the fail-point character before the fail point, which could from a sub-pattern of interest. Prefix/Suffix heuristics helps us pinpoint/eliminate the possibility of such an occurrence.

[@deathbombs]

Sounds really smart

[@jdhruwa]

Great video.. Simple, sufficient and conceptual.. I can`t find any better resource than this to learn KMP algo Thanx a lot

[@thomasnn]

Great video, my book had me all confused about how to fill in the table :)

[@zheyuanxu1938]

it's fairly straightforward

[@blasttrash]

I know its 5 years late but do you remember what book?

[@chaoticmind-z]

THANK YOU!!! I struggled to understand why you go to the value of where (j - 1) is when a mismatch occurs when setting up the Pi table. You are applying the same comparison logic here when setting up the table that's used when comparing the pattern with another string. The index of where (j - 1) is, is the location of where you should do the next comparison if you get a mismatch. Basically... what you do here is what you do with the KMP algorithm and a string. Finally... I understand thanks to you! God bless.

[@mrudul5018]

Why you left video making. I think you were giving far better explanation in 2015 compared to today's videos on KZbin

[@anshaldwivedi9170]

Sir you are really genius , u make every thing so easy.

[@roh9934]

I cant thank you enough for your help and contribution in my life learning DS and Algo. You are the Man.

[@aishy]

Watched a lecture by Sedgwick on the topic twice, and banged my head with the Deterministic Finite state Automata.. But, you just have a knack of simplifying complex shit.. Hats off !! Coding really made simple..

[@arunvyas27]

Thank you Tushar, I have always tried to escape this algorithm due to its complexity. But with your video i was able to get it in 12:49 mins :) :) Thanks a lot.

[@saranghae3720]

@@sasmitvaidya exactly 😂

[@caesarz7704]

At first I do not understand what you are talking about, then I went to read blogs and books about KMP, I got even more confused. Then I go back here to watch this video again, finally found your method is the simplest way to achieve KMP. Nice job mate!

[@celxiusgaming]

Just had to say that this made understanding a complex algorithm, very simple. Thank you so much for posting this and all the other videos you do!

[@ppcuser100]

Very visualized clear and quick message. Great! In other teacher's lessons formalism sentences kills the idea.

[@sushants2719]

Awesome explanation. I didn't come across any other material that explains KMP as simply as this one. Good work, man.. Keep it up .. :)

[@akshaygupta8618]

awesome sir .. u just made it easier for the students of ipu to clear the exam of ADA😀😀😀😀😀😀😀

[@sriramv4306]

Excellent! Would be interesting to know the logic behind this algorithm, like how it was formulated.

[@muditkhanna8164]

This video made me clear, let me make it more clearer for anyone in comments whenever you find a match of suffix and prefix (pre-requisite concept) ,now you are matching the string the from the next index's of the previous matched prefix-suffix matched element and the text string does not get backtracked that's how it saves time, by not sliding but by jumping.

[@siddharthchabukswar2]

Hello my name is KMP and today I'm going to talk about Tushar.

[@ashishshetty3512]

Lier

[@vikrant4666]

this man is working in apple now , he is great achiever , we should learn from this dude

[@saikumarganganapalli5957]

At 7:29 Why are we filling the lps in that fashion.? Why should look at prev character's stored value? Nice Video Although

[@jap963852741]

Awesome, His video is always the easiest to get the core knowledge about the algorithm.

[@gotoexplore6874]

interesting the sufix-prefix sub algorithm.

[@leemarchelloopperman372]

Great work Tushar, my textbook confused me but this video has given me a better grasp of the kmp algorithm. Thanks alot

[@USIndian51]

While buliding the array at time 5:59, when character at j=0 and i=1 didn't match,you incremented the value of i but at time 7:3o when character 'd' at poistion j=3 didn't match the character 'a' at position, you didn't increment i but looked into the lookup table of the previous chatacter to get the postion of j. So, the question is when there is a mis match when do increment i and when do you peek into the lookup table of the previou character to get position of ? Do we have to handle special cases at the beginning and also the last character in the pattern? You explanation was excellent except for this one doubt.

[@indianfootball2328]

Increment only when there is a match or j=0, If there is mismatch lookup at value j-1 and match again

[@giorgi23]

Idea is that when sequential characters don't match you go back and check for the longest prefix that is the same as the suffix you are standing at. If there is no prefix available then you need to go forward and start comparing characters at the beginning of pattern with the string

[@sheikhomur4897]

Thank you very much sir, This is the easiest way to understand the KMP and described it amazedly.

[@souvikdatta97]

Thanks a lot sir for explaining this so clearly and nicely!

[@jvst7728]

can i say why this video is better than other it is because he has taken a very good example, which was clearing many doubts

[@srishti1613]

Who else thinks that this person looks like Gautam Gambhir. Like here 👇👇

[@Sushil2874]

Exactly..!!

[@mrudul5018]

I was banging my head here and there for KMP and finally got this video.

[@SUPERRICHKIDS]

I can skip this class because of you

[@TY-hr5bn]

Thanks! Great explanation! "The point is where we start in the pattern for the next comparison"

[@compscilaw]

The time complexity to build the next table is O(m) not O(n).

[@witslost]

it is Big O (Big O)) actually

[@compscilaw]

@@witslost You're big square.

[@witslost]

@@compscilaw no i am Big O(square)

[@compscilaw]

@@witslost On the internet, no one is supposed to know you're a dog; but your profile picture gives it away. No one is supposed to know that I'm nine squirrels in a human suit.

[@witslost]

@@compscilaw no i am nine Big Os in a human suit

[@PRANAVMAPPOLI]

Best explanation even after 7 years !

[@boheymiyaan]

Thank you sir :) This video is really helpful. Thanks a lot :)

[@sayakpaul3152]

+Sumit Biswas Totally agreed. Nothing could be better.

[@boheymiyaan]

:)

[@0spidey1]

Thanks a lot man. I was studying from the notes another student took, didn't understand a thing. Downloaded the lecturer's slides, didn't understand a thing. I watched your video for 5 minutes and it all made sense.

[@adigenius04]

Anyone studying this in March(or April) 2020 because they have too much free time due to Corona?

[@alyson4791]

I decided to try my hand at making a compiler and this topic came up and my brain is in agony..

[@Aliennnaa]

hello fellow learner

[@arushsaxena9578]

kzbin.info/www/bejne/qmXbhnRjlq2tr5o refer this Best video ever, Do watch its prefix part

[@keshavrathore5228]

HI bro; pehchana

[@sohamgohel1961]

I am watching this in oct 2023

[@royalbandadancer]

Best simple approach sir I got this video after 3rd skipped video on KMP

[@senthilnathan3834]

What if there is no common prefix and suffix in the pattern?

[@ycjoelin000]

No, since you can skip the characters that were already compared, in the text to be searched, it's still O(m) on search, no matter what the pattern is. So it's total O(m+n). (I know this is a thread about a year ago, just leaving comment for other viewers.)

[@ujjwalrockriser]

I saw so many vedios, but this video is god for me. Thank you so much Tushar Sir. Video quality doesn't matter, teaching quality matters.

[@user-mo3bk6wv6l]

I had to watch this video 5 times in order to fully understand... should I drop out from computer science ?.....

[@marcuspolk240]

No. According to Sedgewick's Algorithms book, this is the trickest algorithm in his book. Apparently when it was first implemented, one of the maintainers couldn't understand it so he replaced it with the brute force implementation.

[@jerwinsamuel]

If you were able to understood it in the end, why does it matter. Congrats 👏

[@ІванМанчур-е7з]

you suck ,I understand it at 4 times.)))

[@SoyJayP]

No

[@kabbu643]

Dude he totally confused me

[@utkarshpandey5-yeariddelec863]

This is indeed the best KMP substring search explanation

[@MrAvtar1]

Best explanation seen so far !! Keep doing this great work.

[@ChumpyZhang]

There are tons of person explaining this KMP algorithm. So far, the most useful one!

[@boyangdong8927]

Nice tutorial. But i personally don't like the sound when you erase i/j by your finger, that hurts my ear. Please use a eraser/cloth.

[@sriniakhilgujulla3892]

lol

[@smbehindyou]

hahaha

[@TM-qc5oz]

You have some serious issues man. Sort them out soon..before you set foot outside ur home..u know people outside make a lot of different sounds..

[@teaandy369]

this is best kmp explanation video so far

[@jmares93]

Tushar you are the man

[@tusharsaini2801]

Amazing Explanation , Just Awesome Explanation of how the Algorithm is working . Thank You For such Great Content

[@farenew5326]

thanks a lot, your explanation is easy to understand, but I think if you could add the source code in your video and then explained it would be better. Anyway ,thanks again :)

[@anktrj]

after more than 5 years of videos being posted! It still feels new! Anyway thanks for the quality content!

[@rikhardu]

~6:10 small MISTAKE: You say that if two characters are the same, you increase VALUE of the first one by 1 and put it in the value field of the second one... actually you increase index of the character, not the value of the function (which is seen later, when you analyse second 'b': 7:12). Fortunately in case of the first 'a' index and value of the function are the same, so nothing changes in the table... it's just a bit harder to understand due to this small mistake. Nevertheless thx for the videos, they are very helpful!

[@Lightyin]

He did say value.... but then again he did also point to the index :)

[@rodrigomolina2055]

also in the point 7 the value is zero not 1, in the final step at minute 7:51

[@YogeshDorbala]

sorry but it is 1

[@joseph1586]

why is 1?

[@evanwang5553]

I think this algorithm is very well explained by Tushar.

[@BharatSingh-zk8lx]

pattern sounds like parrot

[@vincentt.7146]

U made it so easy to understand, disillusioning me to thinking that even i could have come up with this. Amazing, thank you!

[@dhulipalaj]

Very well explained. Searching all over found this nice , detailed explanation

[@nhutranquynh5766]

This is the best KMP video i've seen. You explain very clearly that i can understand eventhough English is not my mother tonge. Thank you very much!

[@tafsiralam1752]

Really your videos are so helpful for us sir....your way to teaching is fabulous.

[@teamsarmuliadi6960]

You made it easy as though there is no problem with KMP algorithm.. Thanks