Find common substring between two strings

string manipulation

substring search

algorithm

programming

coding techniques

Find common substring between two strings

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

Finding the common substring between two strings is a classic problem in computer science and has a wide array of applications, from DNA sequencing to data compression and plagiarism detection. The goal is to identify the longest contiguous sequence of characters that appears in both strings, or to determine all shared substrings of a particular length.

Technical Explanation

A common substring problem can vary slightly in definition based on context. A "substring" is defined as a contiguous sequence of characters within a string. The main challenge is to efficiently identify shared substrings between two strings, particularly the longest common substring.

Algorithms for Finding Common Substrings

1. Brute Force Approach:

Complexity: $O(n \times m \times \min(n, m))$ , where $n$ and $m$ are the lengths of the two strings.
Description: This approach involves generating all possible substrings from one string and checking each one against the other string. Although simple to implement, this approach is highly inefficient for large strings.

2. Dynamic Programming:

Complexity: $O(n \times m)$
Description: Dynamic programming can improve the efficiency significantly. A 2D table (or matrix) is filled where DP[i][j] stores the length of the longest common suffix for substrings X[0..i-1] and Y[0..j-1]. The length of the longest common substring is the maximum value found in this table.
Example:

python

1     def longest_common_substring(X, Y):
2         m, n = len(X), len(Y)
3         DP = [[0] * (n + 1) for _ in range(m + 1)]
4         longest = 0
5         
6         for i in range(1, m + 1):
7             for j in range(1, n + 1):
8                 if X[i - 1] == Y[j - 1]:
9                     DP[i][j] = DP[i - 1][j - 1] + 1
10                     longest = max(longest, DP[i][j])
11                 else:
12                     DP[i][j] = 0
13         return longest

3. Suffix Trees:

Complexity: $O(n + m)$ with construction
Description: Build a suffix tree from one string and search for the longest common substring using the other string. Suffix trees provide a very efficient solution but are complex to implement.

4. Suffix Arrays and LCP Array:

Complexity: $O((n + m) \log(n + m))$
Description: A more space-efficient alternative to suffix trees using suffix arrays and longest common prefix (LCP) arrays.

Applications

Biology: Finding common sequences in DNA strands.
Data Compression: Identifying repeat patterns to reduce storage.
Text Analysis: Plagiarism detection or comparison of textual data.
Networking: Data deduplication in network protocols.

Example Scenario

Consider the two strings "abcdfgh" and "abedfgh". The longest common substring here is "fgh" with a length of 3. Employing dynamic programming, we would construct and fill the table as described previously to efficiently reach this conclusion.

Table Summarizing Key Points

Method	Time Complexity	Space Complexity	Description	Suitable For
Brute Force	$O(n \times m \times \min(n, m))$	$O(1)$	Simple, but inefficient for large strings.	Small datasets
Dynamic Programming	$O(n \times m)$	$O(n \times m)$	Efficient, medium space usage, utilizes a DP matrix.	Medium to large data
Suffix Trees	$O(n + m)$	$O(n + m)$	Complex, efficient, ideal for very large datasets.	Very large datasets
Suffix Arrays & LCP	$O((n + m) \log(n + m))$	$O(n + m)$	Space-efficient alternative to suffix trees.	Large datasets

Conclusion

The problem of finding a common substring between two strings is highly relevant across many domains. While the brute force approach is easy to grasp, it quickly becomes infeasible as dataset sizes increase. Dynamic programming offers a balance of complexity and efficiency, while suffix trees and arrays offer the fastest solutions for very large datasets. Understanding these algorithms ensures that one can tackle this problem effectively in any context.