最长重复子数组

**最长重复子数组**

在计算机科学中，给定两个字符串或序列的最长公共子串（LCS）问题是寻找这两个序列之间的最大公共子序列。这个问题有多种应用，如文本编辑、信息检索和生物信息学等。

**动态规划法**

最长重复子数组可以使用动态规划法来解决。动态规划是一种通过分解大问题为小问题并求解这些小问题的方法，以求出原问题的答案。

下面是使用动态规划法求解最长重复子数组的问题的算法：

def longest_common_subarray(str1, str2):
 m = len(str1)
 n = len(str2)

 # 创建一个二维表格，用于存储最长公共子数组的长度 dp = [[0] * (n +1) for _ in range(m +1)]

 max_length =0 # 遍历两个字符串 for i in range(1, m +1):
 for j in range(1, n +1):
 # 如果当前字符相同，则更新最长公共子数组的长度 if str1[i -1] == str2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 max_length = max(max_length, dp[i][j])
 # 如果当前字符不同，则更新最长公共子数组的长度为0 else:
 dp[i][j] =0 return max_length

str1 = "abcdef"
str2 = "zbcdfg"

max_length = longest_common_subarray(str1, str2)
print("最长重复子数组的长度：", max_length) # 输出：3# 最长重复子数组为“bcd”