hari6988's blog

A question on Longest common Substring (Not subsequence)
By hari6988, 14 years ago, In English
I was studying the Longest common substring problem using DP ...

LCS(s1--p, t1--q) = 1+ LCS(s1--p-1, t1--q-1) if s[p]=t[q]

                                 0 otherwise

This was the solution given in wikipedia... This would give an answer of 0 for the strings "to" and "tom" ... But, shouldnt it be 2 ?? the "to" matches with "to" in tom . But, it compares only the last character and gives the answer`
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
LCS(1,1) = 1
LCS(2,2) = LCS(1,1) + 1 = 2
Other LCS(i,j) = 0
So it seems to be right.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    No, i am talking about LCS(2,3) . It will be 0 ,right ? Shouldnt it be 2 ??

    to
    tom

    In this, to matches in both strings ...
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes, you right, but answer is maximum among all LCS(i,j), not LCS(n,m).
      → Reply