Блог пользователя hari6988

Автор hari6988, 13 лет назад, По-английски
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`
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
LCS(1,1) = 1
LCS(2,2) = LCS(1,1) + 1 = 2
Other LCS(i,j) = 0
So it seems to be right.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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 ...