Hello friends, my name is Tushar and today I'm going to talk about the logic
for building the prefix array for the KMP Search
So yesterday i created a video on KMP search and I think I missed a critical
point on how to build the prefix
array. So, I'm creating this video to add to the logic of building prefix array
Thanks to Aditya Joshi who provided critical inputs for this video.
if you have not already checked out the other video, please go and check out that
video for the full explanation of the KMP Substring Search.
Well, this video is just going to concentrate on the prefix array
building for the KMP. Here, I have a really long pattern which will help us understand
the building of prefix array. So first thing we do is we take a temporary
array of the same size as the pattern. Every point at this temporary array is going
to tell us what is the longest suffix length which is also the same as prefix
at every point.
so initially we start, our first point is always zero and this is our i and this
is our j. So we compare, is the value at i same
as value at j. So, it's not. So, since j is zero this value becomes zero and
then we increment our i by one.
then we check is the value at j same as value at i, so it is, so value at two will be
whatever is the value at j plus one so this,
whatever is the value of j. So, that's zero plus one so this becomes one and then
we increment i and j
so what this means is in the substring "aca", there is a suffix of Length one
which is also the prefix, then we check is the value at one
same as value at three, it is, so this becomes value of j which is one plus one.
so, this becomes two. Again in substring "acac" there is a suffix of length two which is
also the prefix and then this becomes two and this becomes four. Again the values
are same
so this value in the temporary array at four will be whatever is the value of j, two plus one three
and then j comes here,
i comes here. Since the value is not same,
our question is what should be the next value of j which we need to compare with
i, so what we do is we go back one, at that index, find
looking in the temporary array so that value is one and then we jump j to that point.
So, j becomes one.
Why did we do that? because that gives us the next highest substring, next
highest substring which is also prefix and suffix.
so this 'a' is a prefix and this 'a' is a suffix so if this 'c' and this 'b' matches, the length
here will be, the length of Suffix here will be of length 2.
right now, it's not a match
so we again go to 'a', the guy before this which is zero and j becomes that value.
So, j becomes zero. So, then we compare is this 'a' same as 'b', it's not.
Now, since this j is zero
this i will become, so the value here will become zero. Again, we will look at it in
little bit more details when we reach the end. So, i comes here
so the value at j is same as value at i, so, the value at six will be whatever is
the value at j plus one so this is one and then we increment both j and i. Value at j
ans i are same, so value here becomes one plus one, so two and then we increment both j and i.
Again, i and j are same,'a' and 'a' so value here will be two plus one three and then we increment
both j and i. Again, values are same, there's a match
so value here becomes four and we increment j and i
It's again a match so, value becomes five, we increment j, we increment i
Again, they match, so value here becomes j plus one six and then we increment j and
increment i. Again, it's a match, so value here becomes seven, we increment j, we increment i
Again they match, so eight, we increment j, we increment i. Again, they match
so this becomes nine which is value of j which is eight plus one nine and then we increment
j and increment i. Again they match, so this becomes ten and then we increment j,
and we increment i. So, again 'a' and 'a' matches. So, this becomes eleven
So what this means is, till this point the longest suffix is of length eleven
which is also a prefix so this suffix is also a prefix. So, suffix from here to
here is also a prefix which is of length
eleven. So, then
j increments by one, i by one now here there is no match
'b' is not same as 'c'. So, our question is what is the next candidate j. You want to
pick the j such that you get the longest, to get the longest
suffix which is also the prefix.
So, what do we know till this point. We know till this point, is that there has been a
match from here.
these two guys have matched till this point. it means that there must be a, this all must be a match
from this point.
so what you do is, you go to 'a'. So, we come here
so basically we reach the tenth point. We check what is the longest prefix,
what is the longest suffix which is also the prefix. so the longest suffix length
which is also a prefix is length five
So, what that means is our j directly jumps here.
why did we do that? because from here the longest suffix which is also prefix
is of length five.
It means that there must be five characters which is suffix and which is
also prefix.
Also we know that since there's a match from this point up to this point, the
length here, whatever the characters are here, must also be the characters at
this point.
What that means is that these five characters must be same as these five
characters. So, our next candidate is j, so, we have already matched the five
characters, we have already matched the five characters and then we're going to
check that this 'b' is same as this 'c' or not
So, again they are different. So, then we're going to look for the next j.
So, again we go back to this point which is four, we check what is the index
what is the value stored at four, so that's three, so then we jump to this
point, so our j becomes three.
Again why we did that? Since this and this was a match but 'c' and 'b' did not
match, we check what is the longest suffix which is also the prefix, so the
longest suffix for this string which is also prefix is of length three.
SO, "aca" and "aca".
Also, we know that this five is same as this five, it means that there must be a
longest prefix here which is also the suffix, which is this three and this three, so
this three and this three. Since they are already a match, so all we're gonna check, is
this 'c' same as this 'c'. At this point, this 'c' is same as this 'c'
so what we do is we store whatever is the value of j plus one, so that's four
so that's how we end up with four for this particular value here. So, hopefully
this helps you understand how to pick the next candidate for the comparison if
there is a mismatch. All you do is you go back one, find the
value in the temporary array, jump to that point and then check if that guy is same
as this guy.
If not, then you repeat the process until your j become zero and if j becomes zero
and it's still a mismatch, then this value will become zero. So, this is all I have to
talk about how to build the prefix array for the KMP. Again if you have
landed on this video first
don't forget to check out my other video on the KMP Search which has all the
other details. Also please like this video, comment on this video, share this
video and check out my facebook page and also check out my Github link at
github.com/mission-peace/interview/wiki
Thanks again for watching this video.