注:子串可不连续,即abc和acd的最长子串长度为2: ac。原理可参考《算法导论》
# 表格驱动的动态规划
import numpy as np
def get_longest_substr_len(str1, str2):
table = np.zeros((len(str1) + 1, len(str2) + 1))
for i in range(1, len(table)):
for j in range(1, len(table[0])):
if str1[i - 1] == str2[j - 1]:
table[i][j] = 1 + table[i - 1][j - 1]
else:
table[i][j] = max(table[i][j - 1], table[i - 1][j], table[i - 1][j - 1])
return table[len(str1)][len(str2)]