Longest Common Substring

Given two strings, find longest common substring between them.

[codr]

@Tushar: I would like to thank you for providing such a awesome information for larger community.

[abhinmankalale]

The guy cracks me up every time he says lets solve it by dynamic programming! Thank you for your videos

[shahirabdullah]

Those who are wondering why did we put '0' in those places where the characters didn't match, since in the longest common sub sequence we took the max of the two adjacent cells instead of putting '0'.

The biggest difference between longest common sub sequence and sub string is the way we interpret dp[i][j].
for Longest common sub sequence, dp[i][j] means the longest common sub sequence between "starting from 0 to i for string s1" and "starting from 0 to j in string s2", .
In contrast,
for Longest common sub string, dp[i][j] means the longest common sub string between S1 and S2 "starting from i and j"
This is very crucial to understand cause this is making all the difference. For sub sequence we are always starting from index 0 and finding out the longest value possible, for sub string we are always starting from the current index and iteratively increasing the value. Since for sub string they need to be consecutive that is why whenever we are finding there's a mismatch we are saying 0 cause starting from i, j so far we have not found any sub string.
hope this helps.

[aniketbhosale]

Your videos are pretty impressive and to the point. I really understand DP problems much better now. Similarly if we have a set of tree and graph interview questions it would be really be helpful thank you :)

[var_guitar]

I think this is the easiest-to-understand video on YT about Longest Common Substring. Thanks!

[rajvis]

Super video! You have explained this so beautifully that even algorithm challenged person like me understood it! Great work!

[rakeshs.r]

It is great that you gave tabular explanation for all.Got an idea of what is happening during

[chenjus]

Another really great, straightforward and clear explanation. Wish you continued making videos.

[nitinjaiman]

First video on youtube which has actually explained dp instead of providing mere formula.

[AyushiSharmaDSA]

thank u tushar for making dp so easy :)

[preethamm.n]

Thank u sir
Now I am enjoying dynamic programming

[ChandraShekhar-bycd]

Thanks a lot for the video. But I think to find the length of the longest substring we should not visit the matrix one more time, instead we can maintain an answer variable which will store the max value each time when we are updating the table. This will help to find the result in single pass.

[mridang]

Best explanation ever.
Dhanyavaad aur pranam

[vishalgandhi]

U are awesome. Explained this in so simple way...

[xxbighotshotxx]

Thank you so much for making these Tushar. You're inspiring confidence in me to be able to do this. I cannot be more grateful. I've already shared this series with classmates :)

[flocela]

so friendly! Thanks for the explanation!

[serhiypidkuyko]

Hi Tushar
Thank you for your video
As for the code: you don't need to create the matrix
Here is the code in python:
#
def longest_common_substr_(s, t):
n=len(s)
uprow=[0]*(n+1)
index=-1
maxlen=0
for x in t:
row=[0]*(n+1)
for j in range(n):
if x==s[j]:
row[j+1]=uprow[j]+1
if row[j+1]>maxlen:
maxlen=row[j+1]
index=j
uprow=row

return s[index+1-maxlen:index+1]
#
def test():
s="abcdef"
t="acbcf"
print(s, t)

substr=longest_common_substr_(s, t)
print(substr)

[akashanand]

Hi, Tushar,
I have one question, while filling 4th row, when char 'c' comes into picture, common substring between "abc" and "zb", still we have length of common substring is 1, then why we are putting '0'.
In short, if character doesn't match, then why we are putting zero, not the max(A[i-1][j], A[i][j-1]). Please clear my concern.By the way, excellent video.

[bensmith]

Thanks for taking the time to explain, but one thing has confused me. Why place zero's in the columns that come after a value greater than zero? eg, col[3][4] 'abcd' and 'zbc', should hold 2, no? since at this point we have a sub-string of "bc"

[swtdrmz]

OH MY GOSH YOU ARE SO AMAZING!!!! THANK YOU FOR THIS WONDERFUL