Go suffixarray.Index.Lookup 怎么查找多次出现的字节片段

在一段已经加载到内存的日志、源码或文档中，如果同一个字节片段会重复出现，Go 标准库的 index/suffixarray 可以避免每次都从头扫描。实际使用时，关键是给 Index.Lookup 传入正确的 n：传 -1 取全部出现位置，传正数只取最多这么多条。返回值是无序的字节偏移，不是字符下标。

官方文档：https://pkg.go.dev/index/suffixarray

先把 n 和返回值语义对齐

Lookup 的签名是 Lookup(s []byte, n int) []int。n 表示返回全部匹配，n>0 表示最多返回 n 个位置，n==0 则直接得到 nil。下面的例子故意使用 ana，因为它在 banana 中从偏移 1 和 3 开始，能够说明重复和重叠位置都不是“只保留第一次”。

package main

import (
	"fmt"
	"index/suffixarray"
)

func main() {
	data := []byte("banana")
	index := suffixarray.New(data)

	// n 为 -1 表示收集全部出现位置；返回值是字节偏移。
	offsets := index.Lookup([]byte("ana"), -1)
	for _, offset := range offsets {
		// 用偏移切回原文，便于把位置和命中的片段一起展示。
		fmt.Printf("offset=%d text=%q\\n", offset, data[offset:offset+len("ana")])
	}
}

这个接口返回的是 []int，而不是带起止位置的二维切片。要得到区间，可以用 offset 和 offset+len(s) 组成；如果只关心前几次命中，则把第二个参数改成正整数，例如 index.Lookup([]byte("ana"), 2)。

字节偏移与结果排序要单独处理

官方文档明确说明返回列表是无序的。因此，文章展示顺序、合并区间或做首次命中判断时，不要默认结果已经从小到大排列。可以复制一份结果后排序，避免改变接口返回值的语义；真实数据量很大时，也可以只在确实需要稳定顺序的出口处排序。

package main

import (
	"fmt"
	"index/suffixarray"
	"sort"
)

func main() {
	data := []byte("Go：查找 Go，记录 Go")
	index := suffixarray.New(data)
	offsets := index.Lookup([]byte("Go"), -1)

	// Lookup 的结果无序；复制后排序，保留原始结果供其他逻辑使用。
	sorted := append([]int(nil), offsets...)
	sort.Ints(sorted)
	for _, offset := range sorted {
		// []byte 的下标按字节计算，中文前缀会让 offset 大于字符数量。
		fmt.Println(offset)
	}
}

第二个坑是字符编码。suffixarray 只认识 []byte，所以偏移落在 UTF-8 字节边界上；它不是 []rune 的元素下标。若要把偏移换成“第几个字符”，应在业务层明确做 UTF-8 边界转换，而不是直接把偏移拿去切 rune 切片。

索引适合重复查询，不适合所有文本搜索

suffixarray.New 建索引的时间复杂度是 O(N)，N 为原始数据长度；一次 Lookup 的复杂度为 O(log(N)*len(s)+len(result))。因此，同一份内存文本会被反复查询时，构建成本容易摊薄；只查一次短字符串时，直接扫描往往更简单。

还要记住三个空结果边界：目标 s 为空、目标不存在或 n==0 时都返回 nil。如果业务把“没有结果”和“索引尚未初始化”混为一谈，最好在调用前单独检查索引状态，并用 len(result)==0 处理查询结果。

常见问题

Lookup 会返回重叠匹配吗？

会。只要字节片段在不同起点出现，重叠位置也属于匹配结果；banana 中的 ana 就会得到 1 和 3。

为什么 Lookup 的结果顺序不稳定？

接口契约只保证返回匹配偏移，不保证升序。需要展示、合并或二分判断时，复制结果后调用 sort.Ints。

中文文本能直接用返回值切字符串吗？

可以切原始 []byte，前提是偏移和长度落在 UTF-8 边界；不能把偏移当成 rune 下标。涉及字符位置时，应另外维护字节到字符的映射。

把 n 的语义、无序返回和字节偏移这三个边界处理好，suffixarray.Index.Lookup 就适合做内存文本上的高频子串定位；如果文本经常修改或只查询一次，则不必为了索引而增加构建和内存成本。