Longest Common Substring in DSA C++ - Deep Dive

Overview - Longest Common Substring

What is it?

The Longest Common Substring problem finds the longest sequence of characters that appears exactly the same and continuously in two given strings. Unlike subsequences, substrings must be contiguous. This problem helps identify shared patterns or overlaps between strings.

Why it matters

Finding the longest common substring helps in many real-world tasks like detecting plagiarism, DNA sequence analysis, and file comparison. Without this concept, it would be hard to efficiently find exact shared parts between texts or data, making many software tools slower or less accurate.

Where it fits

Before learning this, you should understand basic string handling and arrays. After mastering this, you can explore related problems like Longest Common Subsequence and advanced string algorithms like suffix trees and suffix arrays.

Mental Model

Core Idea

The longest common substring is the longest continuous block of characters shared exactly between two strings.

Think of it like...

Imagine two ribbons with colored beads. The longest common substring is like finding the longest stretch of beads with the same colors in the same order on both ribbons without skipping any bead.

String A: a b c d e f g h
String B: x y c d e z

Longest Common Substring:
          c d e

Visual:
A: ...|c|d|e|...
B: ...|c|d|e|...

They match continuously here.

Build-Up - 7 Steps

1

Foundation

Understanding substrings and continuity

Concept: Learn what substrings are and how they differ from subsequences.

A substring is a continuous part of a string. For example, in 'hello', 'ell' is a substring because the letters are next to each other. 'hlo' is not a substring because the letters are not continuous. This continuity is key to the problem.

Result

You can identify substrings by checking continuous slices of a string.

Understanding continuity is essential because the problem only cares about exact continuous matches, not scattered matches.

2

Foundation

Basic string comparison approach

Concept: Compare all possible substrings of one string with the other to find matches.

One naive way is to take every substring of the first string and check if it appears in the second string. For example, for 'abc' and 'bca', check 'a', 'ab', 'abc', 'b', 'bc', 'c' against the second string.

Result

This method works but is very slow for long strings because it checks many substrings.

Knowing this brute force method helps appreciate why more efficient methods are needed.

3

Intermediate

Dynamic programming table setup

Concept: Use a 2D table to store lengths of matching substrings ending at each position.

Create a table where rows represent characters of the first string and columns represent characters of the second string. Each cell stores the length of the longest common substring ending at those positions. If characters match, add 1 to the diagonal cell's value; else 0.

Result

The table helps find the longest continuous match by building on smaller matches.

This step shows how breaking the problem into smaller parts and storing results avoids repeated work.

4

Intermediate

Filling the DP table and tracking max length

🤔Before reading on: do you think the longest substring length is found by summing all matches or by tracking the maximum cell value? Commit to your answer.

Concept: While filling the table, keep track of the maximum value found, which represents the longest common substring length.

For each pair of characters, if they match, set dp[i][j] = dp[i-1][j-1] + 1; else 0. Update max length and record the position when a new max is found.

Result

At the end, max length and position give the longest common substring and where it ends.

Tracking the maximum during table filling avoids scanning the table again later, improving efficiency.

5

Intermediate

Extracting the longest common substring

Concept: Use the position and length from the DP table to get the substring from the original string.

Once you know the end position and length, slice the first string from (end - length + 1) to end to get the substring.

Result

You get the exact longest common substring shared by both strings.

Knowing how to extract the substring from indices connects the DP results back to the original problem.

6

Advanced

Optimizing space with rolling arrays

🤔Before reading on: do you think we need to keep the entire DP table or just part of it to find the longest substring? Commit to your answer.

Concept: Since each DP cell depends only on the previous row, we can use two arrays instead of a full 2D table to save memory.

Use two 1D arrays: one for the current row and one for the previous row. Update them as you iterate through characters, keeping track of max length and position.

Result

Memory usage reduces from O(m*n) to O(min(m,n)), where m and n are string lengths.

Understanding dependencies in DP lets you optimize memory without losing correctness.

7

Expert

Suffix automaton for longest substring

🤔Before reading on: do you think suffix automaton can find longest common substring faster than DP? Commit to your answer.

Concept: A suffix automaton is a powerful data structure that can find the longest common substring in linear time by representing all substrings of one string.

Build a suffix automaton for the first string, then traverse it with the second string to find the longest substring present in both. This approach is faster for very long strings.

Result

Longest common substring found in O(m + n) time, much faster than DP for large inputs.

Knowing advanced data structures like suffix automata unlocks efficient solutions for large-scale problems.

Under the Hood

The dynamic programming solution builds a 2D table where each cell dp[i][j] stores the length of the longest common substring ending at positions i in the first string and j in the second. If characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise, it resets to zero. This ensures only continuous matches are counted. The maximum value in this table corresponds to the longest common substring length. The suffix automaton internally represents all substrings of a string as states and transitions, allowing quick traversal to find common substrings.

Why designed this way?

The DP approach was designed to break down the problem into overlapping subproblems, avoiding repeated substring checks. It trades memory for speed. The suffix automaton was developed to handle large strings efficiently by compressing substring information into a graph structure, enabling linear-time queries. Alternatives like suffix trees exist but are more complex to implement.

DP Table Example:

    0  a  b  c
  +------------
0 | 0  0  0  0
a | 0  1  0  0
b | 0  0  1  0
c | 0  0  0  1

Longest common substring length = 1 at dp[3][3]

Suffix Automaton:

[Start] --a--> [State1] --b--> [State2] --c--> [State3]
Each state represents substrings ending at that point.

Myth Busters - 4 Common Misconceptions

Quick: Does the longest common substring always appear at the start of one of the strings? Commit yes or no.

Common Belief: The longest common substring must start at the beginning of one of the strings.

Reality: The longest common substring can appear anywhere in both strings, not necessarily at the start.

Why it matters: Assuming it starts at the beginning can cause incorrect solutions that miss valid substrings elsewhere.

Quick: Is the longest common substring the same as the longest common subsequence? Commit yes or no.

Common Belief: Longest common substring and longest common subsequence are the same problem.

Reality: They differ: substrings require continuity, subsequences do not. So results can be very different.

Why it matters: Confusing these leads to wrong algorithms and wrong answers.

Quick: Can the longest common substring be found by just checking character frequencies? Commit yes or no.

Common Belief: Matching character counts or frequencies is enough to find the longest common substring.

Reality: Frequency alone doesn't capture order or continuity, so it cannot find the longest common substring.

Why it matters: Relying on frequency leads to incorrect matches and misses the continuous requirement.

Quick: Does the DP table store the substring itself? Commit yes or no.

Common Belief: The DP table cells store the actual substring strings.

Reality: The DP table stores only lengths of matching substrings, not the substrings themselves.

Why it matters: Expecting substrings in the table can confuse implementation and memory usage.

Expert Zone

1

The DP approach can be optimized by processing the shorter string as columns to reduce memory usage.

2

Suffix automaton construction is complex but allows solving multiple substring queries efficiently after one build.

3

Longest common substring length can be found without storing the entire DP table by careful rolling array usage.

When NOT to use

For very large strings or multiple queries, DP is inefficient; use suffix automaton or suffix trees instead. If approximate matches are needed, longest common substring is not suitable; consider edit distance or approximate matching algorithms.

Production Patterns

In production, longest common substring is used in plagiarism detection by comparing documents, in bioinformatics to find shared DNA sequences, and in diff tools to highlight exact matching parts between files.

Connections

Longest Common Subsequence

Related problem with relaxed continuity requirement

Understanding the difference clarifies when to use substring vs subsequence algorithms.

Suffix Trees

Advanced data structure that builds on substring concepts

Knowing suffix trees helps solve substring problems faster and handle multiple queries efficiently.

Genetics and DNA Sequencing

Application domain where substring matching finds shared genetic patterns

Realizing substring algorithms help decode biological data shows the practical impact beyond computer science.

Common Pitfalls

#1 Using nested loops to check all substrings without optimization

Wrong approach:

for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
string sub = s1.substr(i, j - i + 1);
if (s2.find(sub) != string::npos) {
// update max
}
}
}

Correct approach:

Use dynamic programming to build a table of matching substring lengths instead of checking all substrings explicitly.

Root cause:

Not realizing the brute force approach is too slow and that DP can reuse previous computations.

#2 Resetting DP cell to previous value instead of zero on mismatch

Wrong approach:

if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = dp[i-1][j-1];

Correct approach:

if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = 0;

Root cause:

Misunderstanding that substring continuity breaks on mismatch, so length must reset.

#3 Extracting substring from wrong indices after DP completion

Wrong approach:

string result = s1.substr(maxIndex, maxLength);

Correct approach:

string result = s1.substr(maxIndex - maxLength + 1, maxLength);

Root cause:

Confusing end position with start position of the substring.

Key Takeaways

Longest common substring finds the longest continuous matching part between two strings.

Dynamic programming efficiently solves this by building a table of matching substring lengths.

Tracking the maximum length during DP table filling avoids extra passes.

Advanced structures like suffix automata solve this problem faster for large inputs.

Understanding substring continuity is key to distinguishing this problem from similar ones.

Practice

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

easy

A. The longest sequence of characters that appear contiguously in both strings

B. The longest sequence of characters that appear in both strings but not necessarily contiguously

C. The total number of common characters between the two strings

D. The longest string formed by concatenating 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 any breaks.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, which allows gaps, Longest Common Substring requires characters to be contiguous in both strings.

3. Final Answer:

   The longest sequence of characters that appear contiguously in both strings -> Option A

4. Quick Check:

   Longest Common Substring = contiguous matching characters [OK]

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

Common Mistakes:

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

2. Which of the following C++ code snippets correctly initializes a 2D vector dp of size m+1 by n+1 with all zeros for Longest Common Substring?

easy

A. std::vector dp(m+1, std::vector<int>(n+1, 0));

B. std::vector<int> dp(m+1, std::vector<int>(n+1, 0));

C. std::vector dp(m, std::vector<int>(n));

D. std::vector dp(m+1, n+1, 0);

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector with m+1 rows and n+1 columns filled with zeros, use nested vector initialization.

2. Step 2: Check each option

   std::vector dp(m+1, std::vector<int>(n+1, 0)); correctly creates a vector of vectors with m+1 rows, each row a vector of n+1 zeros. Others have syntax errors or wrong types.

3. Final Answer:

   std::vector dp(m+1, std::vector<int>(n+1, 0)); -> Option A

4. Quick Check:

   Correct 2D vector initialization = std::vector dp(m+1, std::vector<int>(n+1, 0)); [OK]

Hint: Use nested vector constructor for 2D zero initialization [OK]

Common Mistakes:

• Using wrong vector types in initialization
• Missing inner vector initialization
• Trying to pass three arguments to vector constructor

3. What is the output of the following C++ code snippet?

std::string s1 = "abcdxyz";
std::string s2 = "xyzabcd";
int m = s1.size(), n = s2.size();
std::vector dp(m+1, std::vector<int>(n+1, 0));
int maxLen = 0;
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    if (s1[i-1] == s2[j-1]) {
      dp[i][j] = dp[i-1][j-1] + 1;
      maxLen = std::max(maxLen, dp[i][j]);
    }
  }
}
std::cout << maxLen << std::endl;

medium

A. 3

B. 4

C. 1

D. 0

Solution

1. Step 1: Trace matching substrings

   The longest common substring is "abcd" (length 4), which appears contiguously at the start of s1 and end of s2. "xyz" is length 3.

2. Step 2: Check dp updates and maxLen

   dp updates length for matching characters. The longest continuous match found is length 4 for "abcd".

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Longest common substring length = 4 [OK]

Hint: Check continuous matching segments, not total matches [OK]

Common Mistakes:

• Confusing substring with subsequence length
• Counting non-contiguous matches
• Off-by-one errors in indexing

4. Identify the bug in the following C++ code snippet for Longest Common Substring:

std::string s1 = "abcde";
std::string s2 = "abfde";
int m = s1.size(), n = s2.size();
std::vector dp(m+1, std::vector<int>(n+1, 0));
int maxLen = 0;
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    if (s1[i] == s2[j]) {
      dp[i][j] = dp[i-1][j-1] + 1;
      maxLen = std::max(maxLen, dp[i][j]);
    }
  }
}
std::cout << maxLen << std::endl;

medium

A. dp vector size should be (m+1) x (n+1) to avoid out-of-bound errors

B. maxLen should be initialized to -1 instead of 0

C. The loop indices should start from 0 instead of 1

D. The comparison should be s1[i-1] == s2[j-1] instead of s1[i] == s2[j]

Solution

1. Step 1: Check string indexing inside loops

   Loop variables i and j start from 1, so to access string characters correctly, indices should be i-1 and j-1.

2. Step 2: Identify the incorrect comparison

   The code compares s1[i] and s2[j], which causes out-of-bound access and wrong comparisons. It should be s1[i-1] == s2[j-1].

3. Final Answer:

   The comparison should be s1[i-1] == s2[j-1] instead of s1[i] == s2[j] -> Option D

4. Quick Check:

   Correct string indexing = i-1 and j-1 [OK]

Hint: Use i-1 and j-1 to index strings when loops start at 1 [OK]

Common Mistakes:

• Accessing string with i or j directly causing out-of-bounds
• Not initializing dp with correct size
• Starting loops at wrong indices

5. Given two strings s1 = "banana" and s2 = "ananas", write a C++ function to find the longest common substring and return it. What is the correct longest common substring?

hard

A. "anana"

B. "nana"

C. "ana"

D. "ban"

Solution

1. Step 1: Understand the longest common substring candidates

   Check substrings common to both strings. "ana" (length 3) appears multiple times in both strings. "anana" is not a substring of both strings contiguously.

2. Step 2: Verify other options

   "nana" length 4 is not a substring of s2; "ban" only in s1; "anana" is not a substring of s2.

3. Final Answer:

   "ana" -> Option C

4. Quick Check:

   Longest common substring between "banana" and "ananas" is "ana" [OK]

Hint: Check all continuous matches, pick longest common substring [OK]

Common Mistakes:

• Choosing longest common subsequence instead of substring
• Ignoring continuity requirement
• Assuming longer substrings without verifying presence