Longest Common Substring

42
1



Given two strings, find longest common substring between them.

Nguồn: https://freecode.com.vn/

42 COMMENTS

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

  2. Why are you taking it as 0 if they are not same?
    Like zb and abc
    should have longest common substring cell as 1 no? You have done 0.
    Why?

  3. The actual recurrence relation for Construction of DP Matrix:

    LCS(i,j)=Max{LCS(i-1,j),LCS(i,j-1),x}

    calculate x:

    if(input[i]==input2[j])

    T[i][j]=T[i-1][j-1]+1

    else

    T[i][j]=0
    For example:
    to caluculate LCS(2,3) i.eThe LCS(Longest common substring) between zb and abc
    since b != c
    x=0 ,
    LCS[i][j-1]=1 & LCS[i-1][j]=0(from the table).
    so max is 1 among the 3.So cell value is 1 .
    Actually Tushar recursive approach in git link is correct while DP approach is wrong.
    Thanks.

  4. if you take matrix cell mat[2][3]…it indicates longest common substring between abc and zb the longest common substring is 1 whereas you got 0 in the cell.You have missed the logic when the i and j are not same we need to consider exclude i or exclude j.

  5. 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"

  6. 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)

  7. oh my fucking god i hate coding but still somehow managed to cheat in microsoft online test and rest is history , i cracked that fucking interview and now i am working in microsoft at 39 a.pa

  8. there is a conflicting information. the matrix value represents the the LCS between 2 strings. e.g. "zb" and "abc". isn't that supposed to be 1 since 'b' is the common letter?

  9. how do we get lexicographically first if there are more than one common substring of same length? @Tushar Roy

  10. I understand from comments below that while checking zb and abc putting 0 at the intersection of b & c helps in the matrix because it helps you get to the accurate solution. But, what is it that drives you to choose 0 and not 1. Just saying that using zero helps get the solution seems like a trick one must know. If this is asked in an interview, I am afraid without knowing this specific trick, one will be unable to solve the problem. Can you provide a logical reason for putting 0 other than just because it gets the right answer.

LEAVE A REPLY

Please enter your comment!
Please enter your name here