/*
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].
*/
fn lcs(s1: &str, s2: &str) -> (usize, String) {
let n: usize = s1.len();
let m: usize = s2.len();
// Convert strings to byte slices for fast indexing
let a: &[u8] = s1.as_bytes();
let b: &[u8] = s2.as_bytes();
// Create DP table initialized with zeros
let mut dp: Vec<Vec<usize>> = vec![vec![0; m + 1]; n + 1];
// Fill DP table
for i in 1..=n {
for j in 1..=m {
if a[i - 1] == b[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
}
}
}
// Reconstruct the LCS sequence
let length: usize = dp[n][m];
let mut lcs_chars: Vec<u8> = vec![0; length];
let mut i: usize = n;
let mut j: usize = m;
let mut index: usize = length;
while i > 0 && j > 0 {
if a[i - 1] == b[j - 1] {
// Character is part of LCS
index -= 1;
lcs_chars[index] = a[i - 1];
i -= 1;
j -= 1;
} else if dp[i - 1][j] > dp[i][j - 1] {
i -= 1; // Move up
} else {
j -= 1; // Move left
}
}
let sequence: String = String::from_utf8(lcs_chars).unwrap();
(length, sequence)
}
fn main() {
let s1: &str = "AGGTAB";
let s2: &str = "GXTXAYB";
let (length, sequence) = lcs(s1, s2);
println!("String 1: {}", s1);
println!("String 2: {}", s2);
println!("Length of LCS: {}", length);
println!("LCS sequence: {}", sequence);
}
/*
run:
String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB
*/
