Write lcs code in Rust
- User
Write lcs code in Rust
Assistant
Okay, here's the Rust code to find the Longest Common Subsequence (LCS) of two strings using dynamic programming. This code will provide both the length of the LCS and the LCS string itself.
use std::cmp; use std::io; // Function to find the length of the Longest Common Subsequence (LCS) fn lcs_length(s1: &str, s2: &str) -> usize { let chars1: Vec<char> = s1.chars().collect(); let chars2: Vec<char> = s2.chars().collect(); let m = chars1.len(); let n = chars2.len(); // Create a DP table (matrix) to store lengths of LCSs. // dp[i][j] will contain the length of LCS of s1[0..i-1] and s2[0..j-1] let mut dp = vec![vec![0; n + 1]; m + 1]; // Build the dp table in bottom-up fashion for i in 1..=m { for j in 1..=n { if chars1[i - 1] == chars2[j - 1] { // If characters match, LCS length increases by 1 dp[i][j] = dp[i - 1][j - 1] + 1; } else { // If characters don't match, take the max length from the previous row or column dp[i][j] = cmp::max(dp[i - 1][j], dp[i][j - 1]); } } } // The bottom-right cell contains the length of LCS for the entire strings dp[m][n] } // Function to find the actual Longest Common Subsequence (LCS) string fn lcs_string(s1: &str, s2: &str) -> String { let chars1: Vec<char> = s1.chars().collect(); let chars2: Vec<char> = s2.chars().collect(); let m = chars1.len(); let n = chars2.len(); // Create the DP table same as in lcs_length let mut dp = vec![vec![0; n + 1]; m + 1]; for i in 1..=m { for j in 1..=n { if chars1[i - 1] == chars2[j - 1] { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = cmp::max(dp[i - 1][j], dp[i][j - 1]); } } } // Backtrack from dp[m][n] to reconstruct the LCS string let mut lcs = String::new(); let mut i = m; let mut j = n; while i > 0 && j > 0 { // If current characters match, they are part of LCS if chars1[i - 1] == chars2[j - 1] { lcs.push(chars1[i - 1]); i -= 1; j -= 1; } // If characters don't match, move in the direction of the larger LCS length else if dp[i - 1][j] > dp[i][j - 1] { i -= 1; } else { j -= 1; } } // The LCS string is built backwards, so reverse it lcs.chars().rev().collect() } fn main() { let mut s1 = String::new(); let mut s2 = String::new(); println!("Enter the first string:"); io::stdin().read_line(&mut s1).expect("Failed to read line"); let s1 = s1.trim(); // Remove trailing newline println!("Enter the second string:"); io::stdin().read_line(&mut s2).expect("Failed to read line"); let s2 = s2.trim(); // Remove trailing newline println!("\nString 1: {}", s1); println!("String 2: {}", s2); let length = lcs_length(s1, s2); println!("\nLength of the Longest Common Subsequence: {}", length); let sequence = lcs_string(s1, s2); println!("The Longest Common Subsequence is: \"{}\"", sequence); // --- Example Test Cases --- println!("\n--- Example Test Cases ---"); let str1 = "AGGTAB"; let str2 = "GXTXAYB"; println!("\nStrings: \"{}\", \"{}\"", str1, str2); println!("LCS Length: {}", lcs_length(str1, str2)); // Expected: 4 println!("LCS String: \"{}\"", lcs_string(str1, str2)); // Expected: "GTAB" let str3 = "ABCBDAB"; let str4 = "BDCAB"; println!("\nStrings: \"{}\", \"{}\"", str3, str4); println!("LCS Length: {}", lcs_length(str3, str4)); // Expected: 4 println!("LCS String: \"{}\"", lcs_string(str3, str4)); // Expected: "BCAB" or "BDAB" (depends on tie-breaking in backtracking) let str5 = "ABCD"; let str6 = "AEBD"; println!("\nStrings: \"{}\", \"{}\"", str5, str6); println!("LCS Length: {}", lcs_length(str5, str6)); // Expected: 3 println!("LCS String: \"{}\"", lcs_string(str5, str6)); // Expected: "ABD" let str7 = "ABC"; let str8 = "DEF"; println!("\nStrings: \"{}\", \"{}\"", str7, str8); println!("LCS Length: {}", lcs_length(str7, str8)); // Expected: 0 println!("LCS String: \"{}\"", lcs_string(str7, str8)); // Expected: "" let str9 = ""; let str10 = "XYZ"; println!("\nStrings: \"{}\", \"{}\"", str9, str10); println!("LCS Length: {}", lcs_length(str9, str10)); // Expected: 0 println!("LCS String: \"{}\"", lcs_string(str9, str10)); // Expected: "" }Explanation:
-
lcs_lengthfunction:- Takes two string slices (
&str) as input. - Converts them into
Vec<char>to handle Unicode characters correctly and allow easy indexing. - Initializes a 2D vector
dpof size(m+1) x (n+1)with zeros, wheremandnare the lengths of the input strings.dp[i][j]will store the LCS length for the firstichars ofs1and the firstjchars ofs2. - Iterates through the strings (using 1-based indexing for the
dptable) and fills the table based on the standard LCS recurrence relation:- If
chars1[i-1] == chars2[j-1], the LCS length increases by 1 from the diagonal element:dp[i][j] = dp[i-1][j-1] + 1. - If characters don't match, the LCS length is the maximum of the lengths obtained by excluding the last character of
s1(dp[i-1][j]) or the last character ofs2(dp[i][j-1]).
- If
- Finally, returns
dp[m][n], which holds the LCS length for the complete strings.
- Takes two string slices (
-
lcs_stringfunction:- Starts similarly to
lcs_lengthby calculating thedptable. - After the table is filled, it reconstructs the actual LCS string by backtracking from the bottom-right cell (
dp[m][n]). - It uses indices
iandj, starting atmandn. - In a loop (
while i > 0 && j > 0):- If
chars1[i-1] == chars2[j-1], it means this character is part of the LCS. It's appended to thelcsstring (which is built in reverse), and bothiandjare decremented. - If the characters don't match, it checks which cell (
dp[i-1][j]ordp[i][j-1]) contributed to the maximum length stored indp[i][j]. It then movesiorjaccordingly (up or left in the conceptual grid). If both are equal, it arbitrarily chooses one direction (here, it prefers moving left by default).
- If
- Since the LCS string is built by appending characters from the end, the resulting
lcsstring needs to be reversed before being returned.
- Starts similarly to
-
mainfunction:- Prompts the user to enter two strings.
- Calls
lcs_lengthandlcs_stringto get the results. - Prints the length and the sequence.
- Includes several hardcoded examples to demonstrate functionality.
This code provides a standard and efficient way to compute the LCS in Rust.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.