Hello friends my name is Tushar and today we are going to look at the
question
longest common substring.So the question is given 2 strings find the longest
common substring between them.
So for this particular 2 strings the longest common substring will be 'bcd'.
Note how it is different from the longest common subsequence.The longest
common subsequence for these two is 'bcdf'.
But since we're just talking longest common substring the longest common
substring here is 'bcd','bcd' and the length is 3. So how do we solve this
problem, yes using dynamic programming.
So here on the first row I have the 1st,1st string 'abcdaf' and in the
1st column
I have the 2nd string 'zbcdf'. Right,so now we'll populate this matrix and
we'll get the results from there.
Alright so now we'll just look at these two guys
if,if you had 2 strings 'a' and 'z',the longest common substring between them is
of length 0,If you had string 'ab' and and 'C' the longest common substring
between them again will be of 0. If you have string
'abc' and 'z', the longest common substring will be 0.
So what this represents is if you had 1 string
'abcdaf' and another strings 'z', the longest common substring between them is going
to be 0.
Now let's include 'b'. So if you had string 'a' on one side and 'zb' on the
other side, the longest common substring again would be 0.
Let's look at this since 'b' and 'b' are same the longest common substring will be the
1 plus whatever is diagonally across, so 1.
What this means is that we had string 'a' and 'b' and we have string 'z' and 'b'.Now since
'b' and 'b' are same the longest common substring here will be 1 plus and
then we
remove this 2 guys from the picture and whatever is the longest common
substring between 'z' and 'a' which is 0, so 1 plus 0 is 1 so here the longest common,
since they are not same then we call them 0. If the, if the characters are
not same,then we just put 0.
Let's move to this row.
So again 'a' and 'c' are not same,so 0,'b' and 'c' are not same,so 0.Here 'c' and 'c' are same so
the longest common substring between 'z','b' and 'c' ,'a','b' and 'c' is 1 plus what is diagonally
across so 2.
Again we remove 'c' from the picture so because we get ,'c' is already
contributing 1 then we look, look at the longest common substring between 'a' and 'b'
and 'zb' and that is 1 so that 1 plus this 1 so that's 2.
They are different, again 'd' and 'c' are different,so 0,'a' and 'c' are different so 0,
'f' and 'c' are different so 0.
All right let's move on to this row.'d' and 'a' our different, so 0,0,0.Now here 'd' and 'd' are
same so the longest common substring will be what is across plus 1 so 3.Again
'a' and 'd' are different so 0 and 0.
Let's fill up the last row.0,0,0,0,0 so 'f' and 'f' are same so the longest common
substring will be 0+1,1.
Once this matrix has built all you have to do is iterate through this matrix again
and look for the biggest number so that number is 3 so this is showing me
the longest,length of the longest common substring.If someone asks you what is
that substring is? So all you have to do is go to the biggest number,
so 3,so 3 is definitely,this row and this column is definitely at the end in the
answer 3,'d' is one of them. Then you keep going diagonally across, so 'c' and 'c' is
one of them and then you keep going diagonally across and
then 'b' and 'b' is one of them.And then as soon as you hit 0, you know you're done.
So our longest common substring is 'bcd' and the length is 3.
Let's look at the formula for this one.
If input1[i]
is equal to equal to input2[j] then T[i][j] is equal to T[i-1][j-1]
plus 1 else T[i][j]
is equal to 0. If you want the full solution go to my github link
github.com/mission-peace/interview/wiki.
Thanks for watching this video.