使用自底向上方法进行动态编程的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”的方法，该方法使用两个字符串作为参数。
迭代这两个字符串，并检查在两个字符串中是否都找到匹配的字符串。
即使找到单个字符，它也会存储在另一个变量中。
当这种情况一直持续到字符串末尾时，这两个字符串将共用另一个字符串。
定义了两个字符串，并通过传递这两个字符串来调用该方法。
该操作的数据分配给一个变量。
然后将其显示为控制台上的输出。