如何高效查找两个列表中最长连续匹配元素序列及起始索引

给定两个列表：

a = [
    'Okay. ',
    'Yeah. ',
    'So ',
    'my ',
    'thinking ',
    'is, ',
    'so ',
    'when ',
    "it's ",
    'set ',
    'up ',
    'just ',
    'one ',
    'and ',
    "we're ",
    'like ',
    'next ',
    'to ',
    'each ',
    'other '
]

b = [  
    'Okay. ',
    'Yeah. ',
    'Everything ',
    'as ',
    'normal ',
    'as ',
    'possible. ',
    'Yeah. ',
    'Yeah. ',
    'Okay. ',
    'Is ',
    'that ',
    'better? ',
    'Yeah. ',
    'So ',
    'my ',
    'thinking ',
    'is, ',
    'so ',
    'when '
]

两列表元素存在部分差异，但包含连续匹配的子序列。例如：

• 前2个元素匹配，对应序列为['Okay. ', 'Yeah. ']
• 更长的匹配序列为['Yeah. ', 'So ', 'my ', 'thinking ', 'is, ', 'so ', 'when ']，长度为7，是当前最长匹配序列，需要获取它在列表a中的起始索引（应为1）和列表b中的起始索引（应为13）。

暴力枚举法虽然可行，但效率低下，以下是更优的动态规划解法：

解法思路 #

采用滚动数组优化的动态规划，核心逻辑：

• 定义dp[j]表示以当前遍历到的a元素和b[j-1]元素结尾的最长连续匹配子序列长度
• 遍历a的每个元素，逆序遍历b的元素（避免覆盖上一轮的状态）
• 当a[i-1] == b[j-1]时，dp[j] = dp[j-1] + 1，同时更新最长匹配长度及对应的起始索引
• 当元素不匹配时，dp[j] = 0

这种方法将空间复杂度从常规二维DP的O(m*n)优化到O(min(m,n))，时间复杂度保持O(m*n)，比暴力法效率提升显著。

代码实现 #

a = [
    'Okay. ',
    'Yeah. ',
    'So ',
    'my ',
    'thinking ',
    'is, ',
    'so ',
    'when ',
    "it's ",
    'set ',
    'up ',
    'just ',
    'one ',
    'and ',
    "we're ",
    'like ',
    'next ',
    'to ',
    'each ',
    'other '
]

b = [  
    'Okay. ',
    'Yeah. ',
    'Everything ',
    'as ',
    'normal ',
    'as ',
    'possible. ',
    'Yeah. ',
    'Yeah. ',
    'Okay. ',
    'Is ',
    'that ',
    'better? ',
    'Yeah. ',
    'So ',
    'my ',
    'thinking ',
    'is, ',
    'so ',
    'when '
]

max_len = 0
start_a = 0
start_b = 0
# 使用滚动数组，空间复杂度为O(len(b))，若len(a)更短可交换遍历顺序优化空间
dp = [0] * (len(b) + 1)

for i in range(1, len(a) + 1):
    # 逆序遍历b，防止覆盖上一轮dp[j-1]的值
    for j in range(len(b), 0, -1):
        if a[i-1] == b[j-1]:
            dp[j] = dp[j-1] + 1
            if dp[j] > max_len:
                max_len = dp[j]
                start_a = i - max_len
                start_b = j - max_len
        else:
            dp[j] = 0

print(f"最长匹配序列长度: {max_len}")
print(f"列表a中的起始索引: {start_a}")
print(f"列表b中的起始索引: {start_b}")

输出结果 #

最长匹配序列长度: 7
列表a中的起始索引: 1
列表b中的起始索引: 13

内容的提问来源于stack exchange，提问作者connor449