Longest Common Substring in c#

General
1

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

  1. Dynamic Programming Table: Create a 2D array dp where dp[i][j] will store the length of the longest common substring that ends with str1[i-1] and str2[j-1].

  2. Initialization: Initialize the table with zeros. The dimensions of the table will be (m+1) x (n+1), where m is the length of str1 and n is the length of str2.

  3. Filling the Table:

    • Loop through each character of both strings.
    • If the characters match (str1[i-1] == str2[j-1]), then set dp[i][j] = dp[i-1][j-1] + 1.
    • If the characters do not match, set dp[i][j] = 0.

  4. Track the Maximum Length: Keep track of the maximum length found during the table filling process.

  5. 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

  1. Input: The program defines two strings, str1 and str2, to find the longest common substring.
  2. LongestCommonSubstring Function:
    • Initializes a 2D array dp to hold the lengths of common substrings.
    • Sets maxLength to track the maximum length found.
  3. 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 with dp[i, j] = dp[i - 1, j - 1] + 1 and checks if the new length is greater than maxLength.
    • If the characters do not match, dp[i, j] is set to 0.
  4. 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 and str2, 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.

1 Like