Python 中最长的公共子字符串
Python 中的字符串在其中存储了一系列字符以对它们执行各种操作。子字符串是这些字符串的一部分。
在本文中，我们需要找到两个给定字符串之间的最长公共子字符串，并将讨论相同的各种解决方案。
Python 中最长的公共子字符串
子字符串是给定字符串中连续的字符序列。它可以是任何长度。
主要问题是我们已经获得了两个字符串，我们需要找到一个在给定字符串之间共有的子字符串，并且应该是所有可能的公共子字符串中最长的。
Input: str1 = "HaveAAppleRegularly"
str2 = "HaveAnAnApple"
Output: "Apple"
在上面的示例中，我们在给定字符串之间有两个公共子字符串，"Have" 和 "Apple"。但由于"Apple"子字符串的长度是其余子字符串中最长的；因此，它将显示为我们的结果。
可以使用递归和动态规划等各种概念来解决这个问题。
在 Python 中使用循环来查找最长公共子字符串
循环可用于遍历字符串。我们可以在这里使用循环遍历字符串，并在两个给定字符串之间找到我们最长的公共子字符串。
在这种方法中，我们将同时使用 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 中最长的公共子字符串。
-
在给定的寻找最长公共子字符串的问题中，最小的可能输入可以是长度为
0的字符串。因此，基本情况将检查输入的任何长度是否为0，然后该函数应返回0。 -
现在，我们将比较两个字符串的最后一个字符，然后出现两种情况，两个字符匹配或不匹配。
-
如果每个给定字符串的最后一个字符匹配，那么我们应该递归调用其余的字符串。因此，我们将两个字符串的长度都减少
1并在其上加一以计算字符串的长度。 -
但是，如果字符不匹配，则对第一个字符串进行递归调用，将其长度递减
1，然后对第二个字符串进行递归调用以将其长度递减1。 -
两次调用之间的最大长度作为我们的结果。
代码示例：
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 中使用动态编程查找最长的公共子字符串
动态规划的基本思想是找到两个字符串的所有子字符串的长度，并将它们各自的长度存储在一个表中。由于使用递归，可能会出现堆栈溢出错误，因为对于大输入，递归堆栈将不断增加。
我们引入了动态规划的概念，我们在其中形成了一个表格，并将继续存储各个子字符串的结果。我们在递归中使用的相同算法也用于一些更改。
现在，我们将讨论在 Python 中查找最长公共子字符串的步骤。
-
首先，初始化表格的第一列和第一行。正如我们在递归的基本条件中所见，这些单元格将使用值
0进行初始化。 -
我们使用循环而不是递归调用我们的逻辑。
-
在循环内部，如果两个字符串的最后一个字符匹配，我们将特定单元格的长度增加
1。 -
否则，我们将最大长度存储到特定单元格中的相邻行和列。
-
最后，我们的结果将存储在表格的最后一个位置；因此，我们返回
dp[m][n]。
代码示例：
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 中最长的公共子字符串。第三种方法将是本文讨论的解决问题的所有解决方案中最快的方法，应该是首选方法。