The Longest Common Substring problem involves finding the longest substring that appears in both of two given strings. This problem can be solved efficiently using dynamic programming.
Algorithm Explanation
-
Dynamic Programming Table: Create a 2D array
dp
wheredp[i][j]
will store the length of the longest common substring that ends withstr1[i-1]
andstr2[j-1]
. -
Initialization: Initialize the table with zeros. The dimensions of the table will be
(m+1) x (n+1)
, wherem
is the length ofstr1
andn
is the length ofstr2
. -
Filling the Table:
- Loop through each character of both strings.
- If the characters match (
str1[i-1] == str2[j-1]
), then setdp[i][j] = dp[i-1][j-1] + 1
. - If the characters do not match, set
dp[i][j] = 0
.
-
Track the Maximum Length: Keep track of the maximum length found during the table filling process.
-
Return the Result: The maximum length indicates the length of the longest common substring.
C# Implementation
Here’s a sample implementation of the Longest Common Substring problem:
using System;
class Program
{
static void Main()
{
string str1 = "abcdxyz";
string str2 = "xyzabcd";
int result = LongestCommonSubstring(str1, str2);
Console.WriteLine("Length of Longest Common Substring: " + result);
}
static int LongestCommonSubstring(string str1, string str2)
{
int m = str1.Length;
int n = str2.Length;
int[,] dp = new int[m + 1, n + 1]; // DP table to store lengths
int maxLength = 0; // Variable to track the maximum length
// Fill the DP table
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// Check for matching characters
if (str1[i - 1] == str2[j - 1])
{
dp[i, j] = dp[i - 1, j - 1] + 1;
maxLength = Math.Max(maxLength, dp[i, j]); // Update max length
}
else
{
dp[i, j] = 0; // Reset on mismatch
}
}
}
return maxLength; // Return the length of the longest common substring
}
}
Explanation of Code
- Input: The program defines two strings,
str1
andstr2
, to find the longest common substring. - LongestCommonSubstring Function:
- Initializes a 2D array
dp
to hold the lengths of common substrings. - Sets
maxLength
to track the maximum length found.
- Initializes a 2D array
- Filling the DP Table:
- Two nested loops iterate through the characters of both strings.
- When a match is found (
str1[i - 1] == str2[j - 1]
), it updates the DP table withdp[i, j] = dp[i - 1, j - 1] + 1
and checks if the new length is greater thanmaxLength
. - If the characters do not match,
dp[i, j]
is set to 0.
- Return Result: Finally, the function returns
maxLength
, which represents the length of the longest common substring.
Complexity
- Time Complexity: O(m * n), where m and n are the lengths of
str1
andstr2
, respectively. This is due to the nested loops filling the DP table. - Space Complexity: O(m * n) for the DP table.
This dynamic programming approach efficiently computes the longest common substring, providing clarity and performance suitable for moderate-length strings.