如何在数组A中查找数组B的所有出现位置（含起止索引）

嘿，这个问题在数组处理场景里挺常见的，我来分享两种靠谱的解法，从易理解的暴力滑动窗口到高效的KMP算法，你可以根据数据规模来选～

基础解法：滑动窗口暴力匹配 #

核心思路就是把数组B当作一个固定大小的窗口，在数组A上逐个滑动，每次比对窗口内的子数组是否和B完全一致，匹配成功就记录起止索引。

步骤拆解 #

• 边界判断：如果B的长度比A长，或者B是空数组，直接返回空结果（毕竟不可能有匹配）。
• 确定滑动范围：窗口大小等于B的长度，A中有效起始索引的范围是0到len(A) - len(B)（包含），超过这个范围就剩不下足够的元素匹配B了。
• 逐个比对：对每个起始索引i，取出A中从i到i+len(B)-1的子数组，和B比对；匹配成功就记录start_index = i，end_index = i + len(B) - 1。

Python 代码示例 #

def find_all_occurrences(A, B):
    occurrences = []
    len_A, len_B = len(A), len(B)
    
    # 处理边界情况
    if len_B == 0 or len_B > len_A:
        return occurrences
    
    window_size = len_B
    # 遍历所有可能的起始位置
    for i in range(len_A - window_size + 1):
        # 取出当前窗口的子数组
        current_window = A[i:i+window_size]
        if current_window == B:
            occurrences.append({
                "start_index": i,
                "end_index": i + window_size - 1
            })
    return occurrences

# 测试用例
A = [1, 2, 3, 2, 3, 4, 2, 3]
B = [2, 3]
print(find_all_occurrences(A, B))
# 输出: [{'start_index': 1, 'end_index': 2}, {'start_index': 3, 'end_index': 4}, {'start_index': 6, 'end_index': 7}]

这个方法的优点是逻辑简单、容易实现，适合小规模数组；缺点是时间复杂度为O(n*m)（n是A的长度，m是B的长度），数据量大的时候效率会下降。

优化解法：KMP算法（适合大数据量） #

如果数组A和B的长度都很大，暴力匹配的效率就不够看了，这时候可以用KMP算法来优化，时间复杂度能降到O(n+m)。

核心逻辑 #

KMP的关键是预处理数组B，生成一个「前缀函数（部分匹配表）」，记录B中每个位置的最长相等前后缀长度。这样在比对A的时候，一旦出现不匹配的情况，可以利用前缀函数直接调整B的指针位置，不用回溯A的指针，大大减少比对次数。

Python 代码示例 #

def compute_prefix_function(B):
    len_B = len(B)
    prefix = [0] * len_B
    j = 0  # 前缀指针
    for i in range(1, len_B):
        # 不匹配时，回溯到上一个匹配的前缀位置
        while j > 0 and B[i] != B[j]:
            j = prefix[j-1]
        # 匹配时，前缀指针前进，记录长度
        if B[i] == B[j]:
            j += 1
            prefix[i] = j
    return prefix

def kmp_find_occurrences(A, B):
    occurrences = []
    len_A, len_B = len(A), len(B)
    
    if len_B == 0 or len_B > len_A:
        return occurrences
    
    prefix = compute_prefix_function(B)
    j = 0  # B的遍历指针
    
    for i in range(len_A):
        # 不匹配时，根据前缀函数调整B的指针
        while j > 0 and A[i] != B[j]:
            j = prefix[j-1]
        # 匹配时，指针前进
        if A[i] == B[j]:
            j += 1
            # 当B的指针走到末尾，说明找到完整匹配
            if j == len_B:
                start_idx = i - len_B + 1
                occurrences.append({
                    "start_index": start_idx,
                    "end_index": i
                })
                # 调整指针，继续查找下一个匹配
                j = prefix[j-1]
    return occurrences

# 测试KMP方法
A = [1, 2, 3, 2, 3, 4, 2, 3]
B = [2, 3]
print(kmp_find_occurrences(A, B))
# 输出和暴力法一致

这个方法的优点是效率极高，适合处理大规模数组；缺点是逻辑相对复杂一点，需要理解前缀函数的作用。

内容的提问来源于stack exchange，提问作者Onur Kuşçuoğlu