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.
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!
This is the third time I've sat down to look into KMP, but the first time the backwards-prefix-match was explained so I could understand the efficiency of it. Thank you.
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.
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
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!
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!
I wasted my entire life trying to understand this algorithm, and you sir explained it to me in first 5 minutes of the video (That too containing introduction and traditional algo to do same) Thanks a lot. And hats off dude. Amazing. Hope I could give you million like for this one.
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!
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.
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..
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.
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.
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!
@@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.
sir your way of teaching is auwsum rest vedios which i used to see seriously telling make me feel sleepy but your way of teaching kind of holds... the reason maybe u filter the vedio but anyhow i saw ur most of vedios it helped me to learn in a simple matter thanks sir... :)
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.
For most of the complex algos I try to look up if there is a video by Tushar first , very methodical approach with good explanation and a walkthrough of the example.
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.
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
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.
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.)
~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!
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.
@@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.
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 :)
I have been TH-cam user for last 5 years but you know what, this is fist time I'm gonna comment on some video, it's awesome and please keep up the good work (y)
How someone can give such a easy explanation of such a harsh topic...you are awesome sir.
thx.
Damm 8y old comment😮
Bhai abhi aap kya krte ho
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!
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.
After 7 yrs, what you do now sir??
@111rhishishranjan2 after 7 months, what you do now?
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!
This video is great, really clarifies things.
This is the third time I've sat down to look into KMP, but the first time the backwards-prefix-match was explained so I could understand the efficiency of it. Thank you.
this visualization in 5 minutes explained what took me 2 hours reading other sources
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.
দ্য ঃ ডট t do এত দূর
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
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 😊.
The Best explanation of KMP in TH-cam))
12 minutes of helpfull information)))
Beautiful explanation. You address the actual logic of finding the longest suffix that is a prefix in a substring, which it easier to understand.
This was really really helpful...no other video explained KMP algorithm upto this level of clarity...Thanks Tushar Sir!
welcome
what you do now ??
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!
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!
what you do now ??
The only place on YT where I understood KMP !!
Thanks a lottt Sir 🙏
Can the fees that I innocently paid to my college lecturers be taken back and given to you..??
very True. Thank you Tushar for explaining very clearly.
mathur ji emotional(bhavuk) kar diye
i totally agree with you.
zyada bhavuk ho liye :P
I can take the money...:)
old is gold, now this person is working as a technology lead.
You are consistently the best explainer of these concepts. Thank you a ton
One of the best.Tushur is like a saviour who comes helps humanity and never returns back
Just watched this video 5 hours before the exams .. found it so much easy.. God bless you Sir.
Respect from Pakistan...:)
I wasted my entire life trying to understand this algorithm, and you sir explained it to me in first 5 minutes of the video (That too containing introduction and traditional algo to do same)
Thanks a lot. And hats off dude. Amazing. Hope I could give you million like for this one.
this video made KMP pattern matching very simple ... all thanks to tushar
7 years old video, but still one of the best! Thank You Tushar
Wow....This is the best explaination one can ever get on KMP. Thanks alot :)
welcome
@@kamalkishor543210 kuch jyada hi hogya ye toh
I've watched lots of videos about KMP but this explanation is the most useful! Thank you!
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!
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.
The best explanation of the failure table I've found so far. Thanks!
I couldn't understand this earlier. now I'm very clear about this. Such a awesome explanation. Thankyou very much sir.
Very good and simple explanation bro.. Ofcourse we INDIANS are legends in these cases..
Superb explanation. Wow. Had been to so many other channels to understand but in vain. Thanks Tushar.
The first 5 minutes explaining the intuition is time well spent. Thanks Mr. Roy!
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..
A very simple and clear explanation to a seemingly complicated algorithm. Glad I found this.
you are awesome,after watching this vdo KMP algo is very very very very simple for me
Hats off to your teaching style sir
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!
Awesome sir I have never ever understood this kmp in my class as best as u taught.... Congo
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.
Sounds really smart
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.
I cant thank you enough for your help and contribution in my life learning DS and Algo. You are the Man.
Your video is VERY helpful! I think many TH-camrs can be very good teachers in colleges. Thank you Tushar!
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.
this should be the first/pinned comment
THX!
bruh
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!
Awesome explanation. I didn't come across any other material that explains KMP as simply as this one.
Good work, man.. Keep it up .. :)
Great video..
Simple, sufficient and conceptual..
I can`t find any better resource than this to learn KMP algo
Thanx a lot
Me: I will learn KMP.
He: Prefix, Suffix, Suffix, Prefix....
Me: Damn, I am confused... maybe Some other day.
LMAO .. Same here XD
Check out Abdul Bari's video on the same topic. You will surely understand!
lol
@@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.
Some algos you can tackle in one attempt, the others(?) .... you have to grapple with a bit more. :)
Very precise explanation. Examples are used and explained simply.
Great video, my book had me all confused about how to fill in the table :)
it's fairly straightforward
I know its 5 years late but do you remember what book?
Awesome, His video is always the easiest to get the core knowledge about the algorithm.
Hello my name is KMP and today I'm going to talk about Tushar.
Lier
Great work Tushar, my textbook confused me but this video has given me a better grasp of the kmp algorithm. Thanks alot
Why you left video making. I think you were giving far better explanation in 2015 compared to today's videos on TH-cam
sir your way of teaching is auwsum rest vedios which i used to see seriously telling make me feel sleepy but your way of teaching kind of holds... the reason maybe u filter the vedio but anyhow i saw ur most of vedios it helped me to learn in a simple matter thanks sir... :)
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.
@@bulletprooftrading exactly 😂
Number one explanation all of kmp tutorials in utube.
Best explanation of KMP algorithm that i found. Thanks
You are a naturally good teacher Tushar
Search logic first Kmp to understand the complete logic. Excellent explanation with code.
Thanks a lot, Tushar! Your videos made such a long time back are being helpful even today.
I can skip this class because of you
For most of the complex algos I try to look up if there is a video by Tushar first , very methodical approach with good explanation and a walkthrough of the example.
Excellent! Would be interesting to know the logic behind this algorithm, like how it was formulated.
Best video so far I watched for KMP Algorithm, Watching in 2024...
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.
Increment only when there is a match or j=0,
If there is mismatch lookup at value j-1 and match again
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
Superb explanation of failure function with all the scenarios.. and then the actual string matching algo (y)
Thanks a lot sir for explaining this so clearly and nicely!
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.
At 7:29 Why are we filling the lps in that fashion.? Why should look at prev character's stored value? Nice Video Although
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!
Thank you sir :)
This video is really helpful.
Thanks a lot :)
+Sumit Biswas Totally agreed. Nothing could be better.
:)
Very visualized clear and quick message. Great! In other teacher's lessons formalism sentences kills the idea.
interesting the sufix-prefix sub algorithm.
Hands down best videos on algorithms
Who else thinks that this person looks like Gautam Gambhir. Like here
👇👇
Exactly..!!
Explanation for Prefix array building in this video is the best in TH-cam.
Tushar you are the man
From all the other videos on TH-cam, yours are always the best
What if there is no common prefix and suffix in the pattern?
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.)
Really nice explanation, loved it!!
~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!
He did say value.... but then again he did also point to the index :)
also in the point 7 the value is zero not 1, in the final step at minute 7:51
sorry but it is 1
why is 1?
Hi Tushar, Thank you so much. just landed up here when i was searching for substring search. your explanation is so simple.
I had to watch this video 5 times in order to fully understand... should I drop out from computer science ?.....
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.
If you were able to understood it in the end, why does it matter. Congrats 👏
you suck ,I understand it at 4 times.)))
No
Dude he totally confused me
after more than 5 years of videos being posted! It still feels new! Anyway thanks for the quality content!
The time complexity to build the next table is O(m) not O(n).
it is Big O (Big O)) actually
@@witslost You're big square.
@@compscilaw no i am Big O(square)
@@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.
@@compscilaw no i am nine Big Os in a human suit
U made it so easy to understand, disillusioning me to thinking that even i could have come up with this. Amazing, thank you!
Best explanation seen so far !! Keep doing this great work.
I was banging my head here and there for KMP and finally got this video.
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.
lol
hahaha
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..
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
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 :)
This is indeed the best KMP substring search explanation
Anyone studying this in March(or April) 2020 because they have too much free time due to Corona?
I decided to try my hand at making a compiler and this topic came up and my brain is in agony..
hello fellow learner
th-cam.com/video/t4xUA-aHzy8/w-d-xo.html refer this
Best video ever, Do watch its prefix part
HI bro; pehchana
I am watching this in oct 2023
I must admit it took me 3 weeks to get this, but it is not because of you explaining it bad, the technique is actually hard.
Awesome video.
pattern sounds like parrot
Thank you very much sir, This is the easiest way to understand the KMP and described it amazedly.
Sir you are really genius , u make every thing so easy.
I have been TH-cam user for last 5 years but you know what, this is fist time I'm gonna comment on some video, it's awesome and please keep up the good work (y)
Well done with all the videos out there your video was the one where i could understand almost everything
Finally understood it perfectly after so many other videos!