Hello friends, my name is Tushar and today I'm going to talk about KMP
Substring Search
so what is a substring search? Suppose I have a text and i have a pattern. I have to tell
that does this pattern exist in this text or not? So, here my text is "abcbcglx"
and my pattern is "bcgl" so this pattern does exist in this text at this
point here
so in this case my substring search should return 3, the index of the
point from which this pattern exists.
so what is our usual Algorithm to find the substring search
what we usually do is we start from this from the 0th index of the text and 0th
index of pattern and we compare 'b' with 'a'. Since they are not a match,
we go to the next index of text which is 'b' so we compare 'b' with 'b', since
it's a match
we compare 'c' with 'c', again it is a match so we compare 'b' with 'g', at this point
it's not a match
so what we do is we start from the next
letter to our start point. So then we start from 'c' and then we compare 'c' with 'b' again
it's not a match
so again we start from the next point. then we compare 'b' with 'b'
so this is a match and then 'c' is a match, 'g' is a match and 'l' is a match
so in this case we would return 3 which is the index of the point at which text
exist and if our pattern was something like 'bcgll', in that case this
pattern would not be found in the text and we would return an exception or
-1 or something like that.
so how much time would this algorithm take in the worst case, this
algorithm would take O(mn)
time where m is the length of the text and n is the length of the pattern
so this is where KMP Search comes into the picture.
the KMP Search can do the substring search in O(m+n)
time and let's see how KMP Search works
let's understand KMP algorithm using this text and this pattern. So we start
from here. 'a' and 'a' is a match, 'b' and 'b' is a match
'c' and 'c' is a match. 'd' and 'x' is not a match
so this is the point where we find no match
so our aim is to not go backwards in this text
so what we are checking is right before 'd' in this substring, is there a suffix
which is also a prefix of this substring. Since all the characters are
unique
there is no way there can be a suffix which is also a prefix
so what that means is our next comparison will start from 'x' and 'a'
again we'll understand it little bit more in this example so we compare 'a' with 'x'
it's not a match so we move to the next character this 'a' and this 'a' is a match this
'b' and this 'b' is a match
this 'c' is a match, 'd' is a match, 'a' is a match, 'b' is a match
'x' is not a match so again we check in this substring before 'c' from 'a' to
'b'
Is there a suffix which is also a prefix
so if you look here, this "ab" is both the suffix and the prefix of this
pattern
what that means is, since we have matched till 'x' till this point . The character
right before 'x' must be "ab" which is "ab" so what that also means is that since
this is also a prefix
we don't have to match "ab" again and the next match can start from 'x' and 'c'
so what happened here is we didn't have to look backwards in the string to see
where to start the,
where to start the next match from. we can start from right here and here since
this suffix is this
prefix and since this suffix is this prefix and since this "ab" exist here, we've
already matched them and so we start comparing 'c' with 'x'. So 'c' and 'x' is not
same so we chevck, in here, is their a suffix which is also
a prefix? it's not, so finally we start matching 'x' with 'a', so 'x' and 'a' is not same so
we go to the next character, 'a' and 'a' is same, 'b' is same, 'c' is same, 'd' is same, 'a' is same, 'b' is same, 'c' is same
and then, here we have a 'd' and here we have 'y', so again we check in this
substring before 'y'. Is there a suffix which is also a prefix?
so this suffix is also a prefix
what that means is, since we've matched till 'y' this "abc" must be right there that's
"abc".
so what also means is that, since the suffix is also a prefix
there is no reason to compare "abc" again and the next check can start from right
here so this 'd' has to be compared with this one
So this 'd' and this 'd' is same then 'a' is same, 'b' is same, 'c' is same and 'y' is same
so this pattern exists in this text from this point onwards. Hopefully this helps
you understand how the KMP Search works using suffix and prefix
information. So the only thing is how do we do this efficiently?
so in the next section, let's look at that so let's see how we'll efficiently compute
if suffix is same as prefix and what point to start the check if there is a mismatch
in the character between text and pattern
so here we have a pattern "abcdabca", so first is always zero so this is my i and this
is my j. if there is a mismatch
if
i is not same as j so we put zero here and we increment our i, again i is not
same as j, so we put zero here and we increment i.i is not same as j, so we put zero
here and increment i
now i is same as j
so what we do is, the value we put here is whatever is the value of j
which is zero plus one so this becomes one and then we increment
both i and both j
so what this one means? So let's suppose our text was "abcdax" and so on and
our pattern is "abcdab" so there will be a match till this point and this
will be a mismatch right here between 'x' and 'b'. so point is where do we start
the next comparison in the pattern
so since the value here at the index of 'a' is stored one
it means that there is already, there is a prefix which is same length as
the suffix one, so we have already compared this 'a' and this 'a' so the next
point to check will be this 'x' and this 'b'
so this is where this one will come into the picture so again 'b' is same as 'b' so
the value stored here will be the j which is one plus one that is two and then we
increment i and we increment j. 'c' is same as 'c' so we store value two plus one three and then i
goes here and j goes here
so now 'a' is not a match with 'd'
so this is little tricky so what you do is you go to the value on the
previous character so that's zero so j
will become zero and then you compare, is this guy same as this guy
so those guys are same so the value here will be whatever is the value at j
which is zero plus one so this is our temporary array and this array will help
us doing the substring search efficiently. The Time complexity to build
this array is O(n) and the space complexity is also O(n) next let's
look at another example of how to build this array
so here i have a pattern "aabaabaaa" so first is always zero, so i is here, j is
here, since this 'i' is same as 'j' the value here will be the value of j plus one so
this is one and then we increment both i and j so i comes here j comes here this
value is not same as this value so the next point of j will be the value in the
previous character which is zero so j becomes zero this is not same as this
so this value becomes zero and we increment i. this is same as this, so value
here will be j plus one, so this is one and then we increment both i and j. Again this is same as
this, so this becomes two and we increment both j and i. again this
is same as this, so the value here will be two plus one three and we increment both i and j
again they are same so value here will be three plus one equals 4 and we increment i
and then j. Again they are same, so value here will be five and we increment i and then j
at this point 'b' is not same as 'a'
so the next point j will be the value in the previous character which is two
so j jumps directly to two, again this 'a' is not same as this 'a' so j will
jump to the value in here so that's one so j comes to this point. At this point
this 'a' is same as this 'a'
so the value stored here will be whatever at j is one plus one, so this is two
so this is how we build a temporary array for this pattern
so again the time complexity is O(n) and the space complexity is also O(n)
In the next section let's use this array to actually do the substring search
so finally let's apply the substring search on this text for this
pattern so i've prebuilt my array using the logic which we discussed in
the previous section of this video so now we compare 'a' with 'a', so they
are same then 'b' is same, so this 'c' is not same as this 'x'
so then what's the next point, so since we are not going to look back in the original text
we check what is the next point we compare this pattern and this text
so the value, we go back to 'b' and check the value, the value here is zero
so the next point of comparison will be this 'a' and this 'x' because the index
because we're start looking from index zero which is 'a', so this 'a' is not same as this 'x'
so we move forward
this 'a' is same as this 'a', then this 'b' is same as 'b','c' is same as 'c', again 'a' is a
match, 'b' is a match and then at this point, it's not a match
so again we go back here and then two
so what this two is saying is that there is a prefix of length two which is also
a suffix which is clear, this "ab" and this "ab" are prefix and
suffix. what that also means is
that there must be an "ab" in the original text, this "ab", so we can safely
ignore, we can safely ignore this two "ab" and start comparing this 'c' with this 'c'
onwards which is how this two is useful
so we start comparing from the position two in the substring. So 'c' is same as 'c' so
we move forward, 'a' is same as 'a', 'b' is same as 'b' and 'y' is same as 'y'
so this pattern exists in this text
the run time complexity for this algorithm will be O(m) and where m is
the length of this text
the time to build this array, the temporary array is O(n)
and so the total time for this algorithm will be O(m+n) and
the space complexity will be O(n) the code is simple and it's in the
description section of the video so this is all I have to talk about
KMP Search
I would ask my viewers to like this video, share this video and then comment on
this video, also check out my Facebook page and my Github link
github.com/mission-peace/interview/wiki
Thanks again for watching this video.