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

使用自底向上的动态规划查找最长公共子串的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("最长公共子串是:")
if lcw_len > 0:
    print(string_1[lcw_i:lcw_i + lcw_len])

输出

最长公共子串是:
bull

说明

  • 定义了一个名为“compute_lcw”的方法,该方法将两个字符串作为参数。
  • 迭代两个字符串,检查它们是否在两个字符串中找到匹配的字符串。
  • 即使找到单个字符,它也会存储在另一个变量中。
  • 当这样做到字符串的末尾时,另一个字符串将是这两个字符串的共同部分。
  • 定义了两个字符串,并通过传递这两个字符串来调用该方法。
  • 将此操作的数据分配给一个变量。
  • 然后在控制台上显示它作为输出。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程