# 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
longest_common_substring