searching

lcs

function

lcs

number
       A = hieroglyphology
       B = michaelangelo
       Solution = hello | heglo | iello | ieglo
       all length 5

Given two strings A and B, Finds the length of a longest (not necessarily contiguous) subsequence of A that is also a subsequence of B.

@complexityO(|A|·|B|)
  • #subproblems: (|A| + 1) · (|B| + 1)
  • work per subproblem: O(1)
@paramAstring
@paramBstring
@returnsnumber