package main
import (
"fmt"
)
/*
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].
*/
// lcs returns both the LCS length and the actual subsequence.
func lcs(s1, s2 string) (int, string) {
n := len(s1)
m := len(s2)
// Create DP table initialized with zeros
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, m+1)
}
// Fill DP table
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if s1[i-1] == s2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
}
// Reconstruct the LCS sequence
length := dp[n][m]
lcsChars := make([]byte, length)
i, j := n, m
index := length - 1
for i > 0 && j > 0 {
if s1[i-1] == s2[j-1] {
// Character is part of LCS
lcsChars[index] = s1[i-1]
index--
i--
j--
} else if dp[i-1][j] > dp[i][j-1] {
i-- // Move up
} else {
j-- // Move left
}
}
return length, string(lcsChars)
}
func main() {
s1 := "AGGTAB"
s2 := "GXTXAYB"
length, sequence := lcs(s1, s2)
fmt.Println("String 1:", s1)
fmt.Println("String 2:", s2)
fmt.Println("Length of LCS:", length)
fmt.Println("LCS sequence:", sequence)
}
/*
run:
String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB
*/
