Visualization of Knuth-Morris-Pratt String Search Algorithm For implementation and more visit: gbhat.com/algo... This video is created using Manim (github.com/3b1...)
You know, most of the people who try to explain the algorithm do such an extensive explanation, which can leave the student really confused. Visualization of the algorithms is crucial and thank you for creating such a video. It's much easier understanding the idea of KMP without actually knowing all the theoretical stuff first. I am not talking about running it, but actually getting the idea on why this works
one that still confused me. If j is already positioned 0 then why when T[0 - 1] is 0 instead of -1? or is that a special rule when it reached 0 it cant be decrement again?
I don't understand one thing. suppose we have a pattern like this: txt: a a a b a (and so on...) pat: a a a b b lps: 0 1 2 0 0 In this case, where there is a mismatch at the last a and b, I understand why pat is started at 0. because there is no prefix that is also a suffix at that point in the pattern. But why is the txt pointer not shifted back?? How can we be sure that if the pattern is just shifted one place to the right (like in the naive/brute force method) that we won't find a match? meaning: a a a b a ... a a a b b I know in this case it is not a match, but how can we be sure that this is the case always? My question basically is, in this algo, we have a i pointer that is iterating through the txt and a j pointer that is iterating through the pat. when there is a mismatch, the j pattern is shifted back a certain amount (which i understand why) but the i pointer is not shifted at all. THIS is what I don't understand. j pointer is shifted based on if there is a prefix that is also a suffix and that makes sense. But i dont understand why the i pointer is not shifted REGARDLESS of whether a prefix is found or not.
Hi, Thanks for watching the video. At any partial matches, we need to update only j pointer (Index of pattern), because if there was any possible matche it would have been covered in the comparison loop. The below example may make it clear: Text: A B C D A B C D A B D E Pattern: A B C D A B D Table: 0 0 0 0 1 2 0 If we start the comparison using i as pointer to text and j as pointer to pattern. A B C D A B C D A B D E A B C D A B D i=0, j=0 Comparison loop will continue till C != D at i=6, j=6 At this point, we start j from index 2 (Table[5]) since AB is a prefix in pattern and it could be begining of a new match. So the comparison loop continues like this: A B C D A B C D A B D E A B C D A B D i=6, j=2 Working on more examples will make this understanding better. Updating the text pointer would be more inefficient since in real world use cases text will be much larger than pattern like searching for a word in a page or book.
@@gbhat5774 so from your example,at first we begin placing the pointer i at index 0 and then start comparing text with pattern "parralelly" but then after we found a missmatch at index 6, we then jump up the pointer into the index 4 because of the proper prefix which is also suffix properties but we will start comparing the pattern and text from the pattern[2] or from i = 6 because we know that AB would be match anyway.So we know there's some i value that we skipped which is i = 1,i = 2,and i = 3. So how we can prove that there wasn't any match that would be found at i = 1,2,and 3 ?? so then we can safely jump up into index 4 as the start of our string comparison in naive method this can be proven easily because we're using the bruteforce method but how we can prove that at any text index that we skipped by using the kmp algorithm there shouldn't be any match at that index ?? i was still confused at this part....
![[LIVE] : ONE ลุมพินี 76 | คู่เอก "ผึ้งหลวง vs สมิงดำ"](http://i.ytimg.com/vi/9SBshmGQOIM/mqdefault.jpg)
![ง้อ (ALRIGHT) - FOURTH Prod. by URBOYTJ [ OFFICIAL MV ]](http://i.ytimg.com/vi/Qs8ZeV6Dqj8/mqdefault.jpg)
You know, most of the people who try to explain the algorithm do such an extensive explanation, which can leave the student really confused. Visualization of the algorithms is crucial and thank you for creating such a video. It's much easier understanding the idea of KMP without actually knowing all the theoretical stuff first.
I am not talking about running it, but actually getting the idea on why this works
I found this demonstration extremely useful - thank you!
Your step-by-step ppt is good for learning the KMP algorithm or some string matching! Thank you very much!!!
the music is great
Finally Understood!! Perfect Video , Thanks for making this.
Thank you so much i understood kmp algorithm only because of this visualization vedio
one that still confused me. If j is already positioned 0 then why when T[0 - 1] is 0 instead of -1? or is that a special rule when it reached 0 it cant be decrement again?
yes, it's an if case, if it's 0 push the whole window
This algorithm seems to only be beneficial if the pattern has repeating characters. Suppose I had "abcdefg". Wouldn't my lps table contain all zeros?
it would, but the latin alphabet has 26 letters, so they would have to repeat after the 26th letter
thank you so much!
muy buen video muchas gracias
Nice Work! Thanks!
I don't understand one thing. suppose we have a pattern like this:
txt: a a a b a (and so on...)
pat: a a a b b
lps: 0 1 2 0 0
In this case, where there is a mismatch at the last a and b, I understand why pat is started at 0. because there is no prefix that is also a suffix at that point in the pattern.
But why is the txt pointer not shifted back?? How can we be sure that if the pattern is just shifted one place to the right (like in the naive/brute force method) that we won't find a match?
meaning:
a a a b a ...
a a a b b
I know in this case it is not a match, but how can we be sure that this is the case always?
My question basically is, in this algo, we have a i pointer that is iterating through the txt and a j pointer that is iterating through the pat. when there is a mismatch, the j pattern is shifted back a certain amount (which i understand why) but the i pointer is not shifted at all. THIS is what I don't understand. j pointer is shifted based on if there is a prefix that is also a suffix and that makes sense. But i dont understand why the i pointer is not shifted REGARDLESS of whether a prefix is found or not.
Hi, Thanks for watching the video.
At any partial matches, we need to update only j pointer (Index of pattern),
because if there was any possible matche it would have been covered in the comparison loop.
The below example may make it clear:
Text: A B C D A B C D A B D E
Pattern: A B C D A B D
Table: 0 0 0 0 1 2 0
If we start the comparison using i as pointer to text and j as pointer to pattern.
A B C D A B C D A B D E
A B C D A B D i=0, j=0
Comparison loop will continue till C != D at i=6, j=6
At this point, we start j from index 2 (Table[5]) since AB is a prefix in pattern and it could be begining of a new match.
So the comparison loop continues like this:
A B C D A B C D A B D E
A B C D A B D i=6, j=2
Working on more examples will make this understanding better.
Updating the text pointer would be more inefficient since in real world use cases text will be much larger than pattern like searching for a word in a page or book.
@@gbhat5774 so from your example,at first we begin placing the pointer i at index 0
and then start comparing text with pattern "parralelly"
but then after we found a missmatch at index 6,
we then jump up the pointer into the index 4 because of the proper prefix which is also suffix properties
but we will start comparing the pattern and text from the pattern[2] or from i = 6 because we know that AB would be match anyway.So we know there's some i value that we skipped which is i = 1,i = 2,and i = 3.
So how we can prove that there wasn't any match that would be found at i = 1,2,and 3 ??
so then we can safely jump up into index 4 as the start of our string comparison
in naive method this can be proven easily because we're using the bruteforce method
but how we can prove that at any text index that we skipped by using the kmp algorithm
there shouldn't be any match at that index ??
i was still confused at this part....
is this supposed to be the 28. problem leetcode solution?
wow
THX
interesting algo. seems like it can be improved tho