Longest Common Subsequence

Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Scala

def lcs(s: String, t: String): Int = {
  val (m, n) = (s.length, t.length)
  val table = Array.ofDim[Int](s.length + 1, t.length + 1)
  for (i <- 0 to m) {
    for (j <- 0 to n) {
      if (i == 0 || j == 0) 0
      else if (s(i - 1) == t(j - 1)) table(i)(j) = table(i - 1)(j - 1) + 1
      else table(i)(j) = table(i - 1)(j) max table(i)(j - 1)
    }
  }
  table(m)(n)
}

lcs("AGGTAB", "GXTXAYB")

Second Tab