迹忆客 专注技术分享

Python 中的字符串在其中存储了一系列字符以对它们执行各种操作。子字符串是这些字符串的一部分。

在本文中，我们需要找到两个给定字符串之间的最长公共子字符串，并将讨论相同的各种解决方案。

子字符串是给定字符串中连续的字符序列。它可以是任何长度。

主要问题是我们已经获得了两个字符串，我们需要找到一个在给定字符串之间共有的子字符串，并且应该是所有可能的公共子字符串中最长的。

Input: str1 = "HaveAAppleRegularly"
       str2 = "HaveAnAnApple"
Output: "Apple"

在上面的示例中，我们在给定字符串之间有两个公共子字符串，"Have" 和 "Apple"。但由于"Apple"子字符串的长度是其余子字符串中最长的；因此，它将显示为我们的结果。

可以使用递归和动态规划等各种概念来解决这个问题。

循环可用于遍历字符串。我们可以在这里使用循环遍历字符串，并在两个给定字符串之间找到我们最长的公共子字符串。

在这种方法中，我们将同时使用 for 和 while 循环。以下是在 Python 中查找最长公共子字符串需要遵循的步骤。

代码示例：

str1 = "PokemonGo"
str2 = "StopPokemonLetsGo"
result=0
for i in range(len(str1)):
    for j in range(len(str2)):
        k=0
        while ((i + k) < len(str1) and (j + k) < len(str2) and str1[i + k] == str2[j + k]):
            k = k+1
        result = max(result, k)

print("Length of the longest common substring is:", result)

输出：

Length of the longest common substring is: 7

字符串的所有子字符串都可以在 O(n^2) 时间内计算出来，而检查当前子字符串是否与第二个字符串的子字符串匹配则需要 O(m) 时间。上述方法的时间复杂度为 O(n^2 * m)，其中 n 和 m 分别是两个给定字符串的长度。

然而，由于我们没有占用任何额外的空间来实现解决方案，因此上述解决方案的空间复杂度将是 O(1)。

递归是指调用自身的函数。我们需要一个基本案例和递归问题的选择图。

我们将按照以下步骤查找 Python 中最长的公共子字符串。

代码示例：

def LCS(s1, s2, n, m):
    if n == 0 or m == 0:
        return 0

    if s1[n-1] == s2[m-1]:
        return 1+lcs(s1, s2, n-1, m-1)

    else:
        return max(lcs(s1, s2, n, m-1),lcs(s1, s2, n-1, m))
s1 = "pokemonGo"
s2 = "watchPokemon"
n = len(s1)
m = len(s2)
res = lcs(s1,s2,n,m)
print("Length of the longest common substring is:", res)

输出：

Length of the longest common substring is: 7

上述解决方案的时间复杂度为 O(3^(m+n))，空间复杂度为 O(m+n)。

动态规划的基本思想是找到两个字符串的所有子字符串的长度，并将它们各自的长度存储在一个表中。由于使用递归，可能会出现堆栈溢出错误，因为对于大输入，递归堆栈将不断增加。

我们引入了动态规划的概念，我们在其中形成了一个表格，并将继续存储各个子字符串的结果。我们在递归中使用的相同算法也用于一些更改。

现在，我们将讨论在 Python 中查找最长公共子字符串的步骤。

代码示例：

def LCS(X, Y, m, n):

    dp = [[0 for x in range(m + 1)] for y in range(n + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if (X[i-1] == Y[j-1]):
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]
s1 = "playbatball"
s2 = "batballwicket"
n = len(s1)
m = len(s2)
res = lcs(s1,s2,n,m)
print("Length of the longest common substring is:", res)

输出：

Length of the longest common substring is: 7

由于我们的解决方案中只有两个循环，因此上述解决方案的时间复杂度将是 O(m*n)。我们通过形成一个表来存储结果来使用额外的空间。

上述解决方案的空间复杂度为 O(m*n)。

我们已经学习了三种不同的方法来查找两个给定字符串之间的最长公共子字符串。第一种方法是一种简单的方法，使用三个循环并查找给定字符串的所有子字符串，并检查所有子字符串中最长的。

第二种方法使用递归，而第三种方法使用动态编程来查找 Python 中最长的公共子字符串。第三种方法将是本文讨论的解决问题的所有解决方案中最快的方法，应该是首选方法。