/*
This program computes BOTH:
1. The length of the Longest Common Subsequence (LCS)
2. The actual LCS subsequence
It uses an efficient dynamic‑programming algorithm:
Time: O(n * m)
Space: O(n * m)
dp(i)(j) stores the LCS length between:
s1(0..i-1) and s2(0..j-1)
Recurrence:
If characters match:
dp(i)(j) = dp(i-1)(j-1) + 1
Else:
dp(i)(j) = max(dp(i-1)(j), dp(i)(j-1))
After filling the DP table, we reconstruct the LCS by
walking backwards from dp(n)(m).
*/
object LCSApp {
// Function that returns both LCS length and the subsequence
def lcs(s1: String, s2: String): (Int, String) = {
val n: Int = s1.length
val m: Int = s2.length
// Create DP table initialized with zeros
val dp: Array[Array[Int]] = Array.fill(n + 1, m + 1)(0)
// Fill DP table
for (i <- 1 to n) {
for (j <- 1 to m) {
if (s1(i - 1) == s2(j - 1)) {
dp(i)(j) = dp(i - 1)(j - 1) + 1
} else {
dp(i)(j) = math.max(dp(i - 1)(j), dp(i)(j - 1))
}
}
}
// Reconstruct the LCS sequence
val length: Int = dp(n)(m)
val lcsChars: Array[Char] = Array.ofDim[Char](length)
var i: Int = n
var j: Int = m
var index: Int = length - 1
while (i > 0 && j > 0) {
if (s1(i - 1) == s2(j - 1)) {
// Character is part of LCS
lcsChars(index) = s1(i - 1)
index -= 1
i -= 1
j -= 1
} else if (dp(i - 1)(j) > dp(i)(j - 1)) {
i -= 1 // Move up
} else {
j -= 1 // Move left
}
}
(length, lcsChars.mkString)
}
def main(args: Array[String]): Unit = {
val s1: String = "AGGTAB"
val s2: String = "GXTXAYB"
val (length, sequence) = lcs(s1, s2)
println(s"String 1: $s1")
println(s"String 2: $s2")
println(s"Length of LCS: $length")
println(s"LCS sequence: $sequence")
}
}
/*
run:
String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB
*/
