使用自底向上动态规划方法查找最长公共子字符串的 Python 程序

当需要使用自底向上动态规划方法查找最长公共子字符串时，可以定义一个方法来计算较小子问题的解。这些较小子问题的解不需要反复计算。相反，可以在需要时访问它们。这将导致开发出针对手边更大问题的解决方案。

以下是相同内容的演示 -

示例

 在线演示

def compute_lcw(string_1, string_2):
   val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
   for i in range(len(string_1) + 1):
      val[i][len(string_2)] = 0
   for j in range(len(string_2)):
      val[len(string_1)][j] = 0
   lcw_i = lcw_j = -1
   lcw_len = 0
   for i in range(len(string_1) - 1, -1, -1):
      for j in range(len(string_2)):
         if string_1[i] != string_2[j]:
            val[i][j] = 0
         else:
            val[i][j] = 1 + val[i + 1][j + 1]
            if lcw_len < val[i][j]:
               lcw_len = val[i][j]
               lcw_i = i
               lcw_j = j
   return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
   print(string_1[lcw_i:lcw_i + lcw_len])

输出

The longest common substring is :
bull

解释

  • 定义了一个名为“compute_lcw”的方法，该方法将两个字符串作为参数。
  • 这两个字符串被迭代并检查以查看是否在两者中都找到了任何匹配的字符串。
  • 即使找到单个字符，它也会存储在另一个变量中。
  • 当这种情况一直持续到字符串的末尾时，这两个字符串将会有另一个公共字符串。
  • 定义了两个字符串，并通过传递这两个字符串来调用该方法。
  • 此操作的数据被分配给一个变量。
  • 然后将其显示为控制台上的输出。

更新于： 2021年3月11日

232 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告