Longest Common Substring in DSA Rust - Build from Scratch

Longest Common Substring

📖 Scenario: Imagine you are building a simple text comparison tool. You want to find the longest part that two texts share exactly. This helps in finding common phrases or repeated patterns.

🎯 Goal: Build a Rust program that finds the longest common substring between two given strings.

📋 What You'll Learn

Create two string variables with exact given values

Create a variable to store the length of the first string

Use nested loops to find the longest common substring

Print the longest common substring found

💡 Why This Matters

🌍 Real World

Finding common parts of texts is useful in plagiarism detection, DNA sequence analysis, and text editing tools.

💼 Career

Understanding string algorithms and nested loops is important for software developers working with text processing, bioinformatics, and search engines.

1

Create the input strings

Create two string variables called text1 and text2 with these exact values: "ababc" and "babca" respectively.

DSA Rust

# Your code here

Hint

Use let to create string slices with the exact text.

2

Create a variable for the length of the first string

Add a variable called len1 that stores the length of text1 using text1.len().

DSA Rust

fn main() {
    let text1 = "ababc";
    let text2 = "babca";
    // Your code here
}

Hint

Use let len1 = text1.len(); to get the length.

3

Find the longest common substring

Write nested for loops with variables i and j to iterate over text1 and text2. Inside, use a while loop with variable length to find matching substrings. Keep track of the longest substring start index in start and its length in max_len.

DSA Rust

fn main() {
    let text1 = "ababc";
    let text2 = "babca";
    let len1 = text1.len();
    // Your code here
}

Hint

Use as_bytes() to compare characters by index. Update max_len and start when a longer substring is found.

4

Print the longest common substring

Print the longest common substring using println! and &text1[start..start + max_len].

DSA Rust

fn main() {
    let text1 = "ababc";
    let text2 = "babca";
    let len1 = text1.len();
    let mut max_len: usize = 0;
    let mut start: usize = 0;

    for i in 0..len1 {
        for j in 0..text2.len() {
            let mut length: usize = 0;
            while i + length  max_len {
                max_len = length;
                start = i;
            }
        }
    }
    // Your code here
}

Hint

Use println!("{}", &text1[start..start + max_len]); to print the substring.

Practice

1. What does the Longest Common Substring problem find between two strings?

easy

A. The longest sequence of characters that appears in both strings consecutively

B. The longest sequence of characters that appears in both strings but not necessarily consecutively

C. The total number of common characters between two strings

D. The longest string formed by combining both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest continuous sequence of characters that appears in both strings without interruption.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, which allows gaps, Longest Common Substring requires characters to be consecutive.

3. Final Answer:

   The longest sequence of characters that appears in both strings consecutively -> Option A

4. Quick Check:

   Longest Common Substring = consecutive matching characters [OK]

Hint: Look for continuous matching characters in both strings [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking characters can be non-consecutive
• Counting total common characters instead of longest sequence

2. Which Rust code snippet correctly initializes a 2D vector for dynamic programming in Longest Common Substring?

easy

A. let mut dp = vec![vec![0; n + 1]; m + 1];

B. let dp = vec![vec![0; m]; n];

C. let mut dp = vec![vec![0; m + 1]; n];

D. let dp = vec![vec![0; n]; m + 1];

Solution

1. Step 1: Understand dimensions for DP table

   For strings of length m and n, dp table size should be (m+1) x (n+1) to include empty prefixes.

2. Step 2: Check Rust vector initialization syntax

   vec![vec![0; n + 1]; m + 1] creates m+1 rows each with n+1 zeros, matching DP table size.

3. Final Answer:

   let mut dp = vec![vec![0; n + 1]; m + 1]; -> Option A

4. Quick Check:

   DP table size = (m+1) x (n+1) [OK]

Hint: DP table size = (length+1) for both strings [OK]

Common Mistakes:

• Swapping m and n in vector sizes
• Forgetting +1 for empty string row/column
• Using immutable vector when mutability is needed

3. What is the output of this Rust code snippet for strings s1 = "abcde" and s2 = "abfde"?

let s1 = "abcde";
let s2 = "abfde";
let m = s1.len();
let n = s2.len();
let mut dp = vec![vec![0; n + 1]; m + 1];
let mut max_len = 0;
for i in 1..=m {
    for j in 1..=n {
        if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if dp[i][j] > max_len {
                max_len = dp[i][j];
            }
        }
    }
}
println!("{}", max_len);

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Compare characters and fill DP table

   Matching characters are 'a' and 'b' at start, then 'd' and 'e' at the end. The longest continuous match is "ab" with length 2.

2. Step 2: Track max_len during iteration

   max_len updates to 1 for 'a', then 2 for 'b', resets for mismatch, then 1 for 'd' and 1 for 'e'. So max_len = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Longest common substring length = 2 [OK]

Hint: Check consecutive matches, longest is "ab" length 2 [OK]

Common Mistakes:

• Counting non-consecutive matches
• Confusing substring length with subsequence length
• Ignoring reset of dp on mismatch

4. Identify the bug in this Rust code snippet for Longest Common Substring:

let s1 = "hello";
let s2 = "yellow";
let m = s1.len();
let n = s2.len();
let mut dp = vec![vec![0; n]; m];
let mut max_len = 0;
for i in 1..=m {
    for j in 1..=n {
        if s1.as_bytes()[i - 1] == s2.as_bytes()[j - 1] {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if dp[i][j] > max_len {
                max_len = dp[i][j];
            }
        }
    }
}
println!("{}", max_len);

medium

A. Loop ranges should start from 0, not 1

B. DP vector size is incorrect; should be (m+1) x (n+1)

C. Comparison should use chars(), not as_bytes()

D. max_len should be initialized to 1, not 0

Solution

1. Step 1: Check DP vector initialization

   DP vector is initialized with size m x n, but loops access dp[i][j] with i and j starting at 1, causing out-of-bounds error.

2. Step 2: Correct DP vector size

   DP vector should be sized (m+1) x (n+1) to safely access dp[i][j] for i and j in 1..=m and 1..=n.

3. Final Answer:

   DP vector size is incorrect; should be (m+1) x (n+1) -> Option B

4. Quick Check:

   DP size must match loop indices [OK]

Hint: DP size = (length+1) to avoid index errors [OK]

Common Mistakes:

• Using wrong DP vector size causing panic
• Starting loops at 0 but indexing with i-1
• Confusing bytes and chars for comparison

5. Given two strings s1 = "ababc" and s2 = "babca", write a Rust function to find the longest common substring and return it. What is the correct longest common substring?

hard

A. "bab"

B. "babc"

C. "abca"

D. "abc"

Solution

1. Step 1: Use DP to find longest common substring length and end index

   By comparing characters and updating dp, the longest common substring length is 3, ending at index 4 in s1.

2. Step 2: Extract substring from s1 using end index and length

   Substring of length 3 ending at index 4 in s1 is "abc".

3. Final Answer:

   "abc" -> Option D

4. Quick Check:

   Longest common substring = "abc" length 3 [OK]

Hint: Track max length and end index, then slice substring [OK]

Common Mistakes:

• Choosing substring from wrong string
• Confusing substring with subsequence
• Not updating end index when max length changes