如何按连续精确顺序匹配两个Python列表并输出位置标记

需求说明 #

需在长列表中定位所有与目标模式列表完全连续匹配的位置，匹配成功的对应位置标记为"1"，其余位置标记为"0"。原双重循环实现性能不足，需适配长列表（10000元素）+ 长模式（100元素）的高频匹配场景。

方案1：Python风格滑动窗口实现 #

代码简洁易读，依托Python底层C优化的切片比较操作，性能远超手写双重Python循环，足以覆盖绝大多数常规业务场景：

def match_continuous_sub_list(long_list: list, pattern: list) -> list[str]:
    n, m = len(long_list), len(pattern)
    res = ["0"] * n
    if m == 0 or n < m:
        return res
    # 遍历所有合法的窗口起始位置
    for start in range(n - m + 1):
        if long_list[start:start+m] == pattern:
            res[start:start+m] = ["1"] * m
    return res

方案2：KMP算法最优性能实现 #

时间复杂度稳定为O(n+m)（n为长列表长度，m为模式列表长度），无冗余比较，适合超大规模数据（长列表长度≥10万）的匹配场景：

def compute_prefix_function(pattern: list) -> list[int]:
    m = len(pattern)
    pi = [0] * m
    for i in range(1, m):
        j = pi[i-1]
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j-1]
        pi[i] = j + 1 if pattern[i] == pattern[j] else j
    return pi

def kmp_match_continuous(long_list: list, pattern: list) -> list[str]:
    n, m = len(long_list), len(pattern)
    res = ["0"] * n
    if m == 0 or n < m:
        return res
    pi = compute_prefix_function(pattern)
    pattern_ptr = 0
    for idx in range(n):
        while pattern_ptr > 0 and long_list[idx] != pattern[pattern_ptr]:
            pattern_ptr = pi[pattern_ptr - 1]
        if long_list[idx] == pattern[pattern_ptr]:
            pattern_ptr += 1
        # 匹配到完整模式串
        if pattern_ptr == m:
            match_start = idx - m + 1
            res[match_start:match_start + m] = ["1"] * m
            # 允许重叠匹配设为pi[pattern_ptr-1]，禁止重叠设为0
            pattern_ptr = pi[pattern_ptr - 1]
    return res

验证示例 #

以题目给出的示例1测试：

list_1 = ["i", "love", "to", "eat", "fresh", "apples", "yeah", "eat", "fresh"]
list_2 = ["eat", "fresh"]
print(match_continuous_sub_list(list_1, list_2))
# 输出：['0', '0', '0', '1', '1', '0', '0', '1', '1']

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