Python Find the Longest Common Substring of Two Strings

Document 对象参考手册Python3 Examples

The longest common substring problem refers to given two strings, find the longest common substring between them. A substring is a contiguous sequence of characters in a string. We can use dynamic programming to solve this problem.

Example

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)
    # Create a two-dimensional array to store the length of the longest common substring
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0  # Record the length of the longest common substring
    end_pos = 0     # Record the end position of the longest common substring

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0

    # Return the longest common substring
    return s1[end_pos - max_length:end_pos]

# Test
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("The longest common substring is:", result)

Code Explanation:

  1. dpis a two-dimensional array,dp[i][j]represents the strings1the firsticharacters and the strings2the firstjcharacters of the longest common substring length.
  2. We iterate through each character of the two strings, ifs1[i-1]ands2[j-1]are equal, thendp[i][j]the value of ... equalsdp[i-1][j-1] + 1, otherwisedp[i][j]is 0.
  3. max_lengthused to record the length of the longest common substring,end_posused to record the end position of the longest common substring.
  4. Finally, we uses1[end_pos - max_length:end_pos]to obtain the longest common substring.

Output result:

最长公共子串是: bcd

Document 对象参考手册Python3 Examples

Other Extensions