This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

Need Help Understanding Longest Common Substring Problem

# Problem Statement:
# Given two strings, find the length of the longest common substring.
# A substring is a contiguous sequence of characters that appears in both strings.

# Example:
# Input: str1 = "abcdefg", str2 = "bcdfg"
# Output: 4 (The longest common substring is "bcdfg")

# Here's a Python function that solves this problem:

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    
    # Create a table to store the length of the common suffixes of substrings
    # Initialize a variable to store the length of the longest common substring found so far
    # Initialize two variables to store the row and column index of the cell with the maximum value in the table
    
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len = 0
    max_i = 0
    max_j = 0
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    max_i = i
                    max_j = j
    
    # The length of the longest common substring is max_len
    # You can also retrieve the substring itself from the input strings using max_i and max_j
    
    longest_common_substr = str1[max_i - max_len : max_i]
    
    return max_len, longest_common_substr

# Test the function
str1 = "abcdefg"
str2 = "bcdfg"
result, substring = longest_common_substring(str1, str2)
print("Length of Longest Common Substring:", result)
print("Longest Common Substring:", substring)

I came across this interesting problem related to finding the longest common substring between two given strings. I've written a Python function longest_common_substring that should solve the problem. However, I'm having trouble understanding parts of the code, especially the dynamic programming approach used. Could someone explain the logic behind it in more detail? Any insights or alternative solutions are greatly appreciated! Link to the page for reference: Longest Common Substring Problem