寻找多列表中连续匹配子序列的高效优雅Python解法

问题背景 #

给定一个包含多个子列表的集合，需要找出任意两个不同子列表中存在的连续匹配子序列——元素顺序、重复度必须严格一致，因此不能依赖集合类方法。示例如下：

输入：

list_of_lists = [["a", "b", "c"], ["z", "a", "b"], ["y", "b", "c"], ["z", "a"]]

期望输出：

["a", "b"] # 来自第一个与第二个列表
["b", "c"] # 来自第一个与第三个列表
["z", "a"] # 来自第二个与最后一个列表

当前用多层循环实现，但子列表数量达到100级时性能急剧下降，希望找到基于Python工具或库的高效替代方案。

高效实现方案 #

1. 滑动窗口+哈希的成对比对 #

先通过itertools.combinations生成所有不重复的子列表对，再对每一对用滑动窗口结合哈希快速定位最长连续匹配子序列（可按需过滤长度≥2的结果）。这种方法比纯三层循环更高效，哈希比对能大幅减少重复的元素逐次比较。

示例代码：

import itertools

def get_longest_common_contiguous(sub_list_a, sub_list_b):
    # 优先用较短的列表生成窗口，减少计算量
    if len(sub_list_a) > len(sub_list_b):
        sub_list_a, sub_list_b = sub_list_b, sub_list_a
    
    max_possible_len = min(len(sub_list_a), len(sub_list_b))
    # 从最长可能的窗口开始查找，找到即返回（避免冗余）
    for window_length in range(max_possible_len, 1, -1):
        # 预存短列表所有窗口的哈希与对应序列
        window_map = {}
        for i in range(len(sub_list_a) - window_length + 1):
            current_window = tuple(sub_list_a[i:i+window_length])
            window_map[hash(current_window)] = current_window
        
        # 在长列表中滑动窗口匹配哈希
        for i in range(len(sub_list_b) - window_length + 1):
            check_window = tuple(sub_list_b[i:i+window_length])
            if hash(check_window) in window_map:
                return list(window_map[hash(check_window)])
    return None

# 遍历所有子列表对并收集结果
source_list = [["a", "b", "c"], ["z", "a", "b"], ["y", "b", "c"], ["z", "a"]]
match_results = []
for idx1, idx2 in itertools.combinations(range(len(source_list)), 2):
    match_seq = get_longest_common_contiguous(source_list[idx1], source_list[idx2])
    if match_seq:
        match_results.append(
            (match_seq, f"来自第{idx1+1}个与第{idx2+1}个列表")
        )

# 输出结果
for seq, desc in match_results:
    print(f"{seq} # {desc}")

2. 后缀自动机（超大规模场景） #

如果子列表数量极多、元素总量大，后缀自动机是更优选择。它能以O(n)时间构建单个序列的后缀结构，之后可以快速在其他序列中匹配连续子串。你可以手动实现后缀自动机，也可以用第三方简化库（如suffixautomaton）。

3. 关于pandas/numpy的适用性 #

pandas和numpy主要针对结构化数值数据优化，对于这种任意元素的连续子序列匹配，没有原生高效函数。强行套用反而会增加数据转换的开销，不如纯Python的哈希滑动窗口或后缀自动机直接高效。

内容的提问来源于stack exchange，提问作者Petr Průcha