如何基于后缀数组通过二分查找获取子串的全部出现位置？

首先，你方向是对的——后缀数组里所有匹配目标子串的后缀会连续排列，所以只要找到这个连续区间的左右边界，就能拿到所有出现位置。你之前用bisect只拿到一个结果，是因为bisect_left/bisect_right只返回单个边界点，而我们需要同时找到左、右两个边界来圈出整个匹配区间。

核心思路 #

后缀数组是按后缀的字典序排序的，所以所有以目标子串开头的后缀会集中在一起。我们需要：

• 找到左边界：第一个后缀字典序 >= 目标子串的位置
• 找到右边界：第一个后缀字典序 > 目标子串的位置
• 两个边界之间的后缀数组元素，就是子串所有出现的起始索引

实现代码（适配你的示例） #

结合你给出的序列和后缀数组，我写了一个直接可用的实现：

def find_all_occurrences(seq, suffix_array, target):
    n = len(suffix_array)
    target_len = len(target)
    
    # 查找左边界：第一个后缀 >= target
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        # 取后缀的前target_len个字符和target比较（优化：不用取整个后缀）
        suffix_prefix = seq[suffix_array[mid]:suffix_array[mid]+target_len]
        if suffix_prefix >= target:
            right = mid
        else:
            left = mid + 1
    left_bound = left
    
    # 查找右边界：第一个后缀 > target
    right = n
    while left < right:
        mid = (left + right) // 2
        suffix_prefix = seq[suffix_array[mid]:suffix_array[mid]+target_len]
        # 注意：如果后缀长度不足target_len，自然小于target
        if len(suffix_prefix) < target_len:
            left = mid + 1
            continue
        if suffix_prefix > target:
            right = mid
        else:
            left = mid + 1
    
    # 返回所有出现的起始位置
    return suffix_array[left_bound:left]

# 用你的示例测试
seq = "ATGTGCAAGAATGAGGCAAG$"
array = [20, 17, 6, 9, 18, 7, 13, 10, 0, 16, 5, 19, 8, 12, 15, 4, 14, 2, 11, 3, 1]
target = "AAG"
occurrences = find_all_occurrences(seq, array, target)
print(f"子串'{target}'的所有出现位置：{occurrences}")

代码说明 #

• 优化了比较逻辑：只取后缀的前len(target)个字符和目标子串比较，不用生成整个后缀，提升效率
• 处理了后缀长度不足目标子串的情况（比如序列末尾的$后缀）
• 返回的occurrences就是所有匹配的起始索引，对应原序列中seq[start:start+len(target)]就是目标子串

现成实现的情况 #

Python标准库没有专门针对后缀数组的子串匹配工具，但：

• 如果你不想自己实现，一些第三方库比如suffix-array提供了类似功能，但需要额外安装
• 不过上面的代码逻辑简单，依赖少，完全可以自己集成到项目里

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