Python Forum

What is the longest common substring (LCS) of two strings?

The LCS of two strings is the longest sequence of characters that appears in both strings. For example, the LCS of the strings "ABCDGH" and "AEDFHR" is "ADH".

There are many ways to solve the longest common substring in Python. One common approach is to use a dynamic programming algorithm. The following Python code implements a dynamic programming algorithm for the LCS problem:

def lcs(s1, s2):
  n, m = len(s1), len(s2)
  dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

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

  return dp[n][m]


s1 = "ABCDGH"
s2 = "AEDFHR"

lcs = lcs(s1, s2)
print(lcs)

Output:

ADH

What is your preferred approach for solving the LCS problem? Is there a more efficient way to solve the problem?