后缀数组构建不能直接用sort.strings，因其返回字符串副本而非起始下标数组，导致内存o(n²)爆炸且无法还原原始位置；正确做法是用sort.slice对[]int索引排序，按需比较原字符串片段。
后缀数组构建为什么不能直接用 sort.Strings
因为后缀数组本质是所有后缀按字典序排序后的起始下标数组，不是字符串本身排序。用 sort.Strings 会生成一串重复的子串副本，内存爆炸且无法还原原始位置——你真正需要的是 []int 类型的索引序列，比如对 "banana"，要得到 [5,3,1,0,4,2]（对应后缀 "a", "ana", "anana", "banana", "na", "nana" 的起始下标），而不是 ["a","ana","anana","banana","na","nana"]。
常见错误是先生成所有后缀字符串切片再排序，len(s) 长度为 n 时，内存开销是 O(n²)，10MB 文本就可能触发 GC 频繁或 OOM。正确做法是只操作下标，用自定义 sort.Slice + 比较函数，比较时按需截取原字符串片段（注意避免越界）：
sort.Slice(indexes, func(i, j int) bool {
return s[indexes[i]:]
<p>但这个朴素实现仍是 O(n² log n) 时间，实际文本 >100KB 就明显卡顿。</p>
<h3>DC3 算法在 Go 中是否值得手写</h3>
<p>不推荐。DC3 是线性时间后缀数组构造算法，理论最优，但 Go 没有现成高质量实现，手写极易出错：三类后缀分类、基数排序嵌套、递归子问题边界、哨兵处理等细节稍有偏差就会返回错误索引。实测中，对 1MB 文本，DC3 手写版比优化后的倍增法慢 20%，且调试耗时远超收益。</p>
<p>更务实的选择是用已验证的库：<code>github.com/zyedidia/suffixarray</code>（纯 Go，基于倍增法，支持 <code>Search</code> 和 <code>FindAllIndex</code>）或 <code>golang.org/x/exp/suffixarray</code>（标准库实验包，Cgo 加速，但已标记 deprecated，仅限短期项目）。若必须自研，优先实现倍增法（Doubling Algorithm），用 <code>[]int</code> 存 rank，每次迭代用 <code>sort.SliceStable</code> 按二元组 <code>(rank[i], rank[i+k])</code> 排序，k 从 1 开始翻倍。</p>
<p>关键点：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill6460" title="Golang Naming"><img
src="https://img.php.cn/upload/skill/000/000/081/179094616043400.jpg" alt="Golang Naming" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill6460" title="Golang Naming" class="overflowclass">Golang Naming</a>
<p class="overflowclass">Go（Golang）命名规范 — 包括包、构造函数、结构体、接口、常量、枚举、错误、布尔值、接收器、getter/setter、函数等。</p>
</div>
<a rel="nofollow" href="/xiazai/skill6460" title="Golang Naming" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
- 初始 rank 是 byte 值，注意
byte范围是 0–255，中文等 Unicode 字符需先转[]rune或 UTF-8 编码预处理 - 每轮排序后需去重压缩 rank，否则后续比较失效
- 最终 SA 数组长度恒为
len(s)，但若 s 含\x00，某些实现会提前截断，务必用len([]byte(s))而非len(s)初始化
suffixarray.New 构建后如何安全查子串
golang.org/x/exp/suffixarray 的 New 方法返回指针，底层持有原文本的引用——这意味着如果你传入的是局部变量或临时拼接字符串（如 s := strings.Repeat("a", 1e6)），GC 可能提前回收，导致后续 Lookup 返回空结果或 panic。必须确保原文本生命周期覆盖整个索引使用期。
实操建议：
- 把文本存在 struct 字段里，SA 作为同级字段，例如：
type Indexer struct { text string; sa *suffixarray.SuffixArray } - 不要对
string(bytes)结果直接调用New，bytes 若被复用或释放，text 会变成悬垂引用 -
FindAllIndex返回的是[][2]int（每个元素为[start, end)），注意 end 是开区间，切片时别写成s[r[0]:r[1]+1] - 若需频繁查多个子串，别反复调用
FindAllIndex，改用Lookup得到[]int（后缀起始位置），再手动匹配长度——后者省去内部二分搜索开销
内存占用比预期高太多？检查字符串 header 复制
Go 字符串是只读结构体，包含 data 指针和 len，但当你用 s[i:j] 截取子串时，新字符串 header 共享原底层数组。后缀数组构建过程中若大量保存 s[i:] 形式子串（即使只是临时比较），会导致整个原始字符串无法被 GC 回收——哪怕你只索引其中 1KB 内容，100MB 原文本仍驻留内存。
规避方法只有两个：
- 彻底避免生成子串：所有比较逻辑基于下标运算，用
bytes.Compare([]byte(s[i:]), []byte(s[j:])) 替代 <code>s[i:] （虽慢一点，但内存可控） - 若必须缓存子串，显式拷贝：
substr := append([]byte(nil), s[i:]...)，代价是额外 O(n) 内存，但至少不会拖垮全局
真正棘手的是第三方库内部行为——比如某个 suffixarray 实现悄悄缓存了首字符数组用于加速，却没文档说明。遇到内存异常增长，优先用 pprof 查 runtime.MemStats 和 heap profile，重点看 inuse_objects 和大块 []byte 分配来源。
golang免费学习笔记（深入）：立即使用
在学习笔记中，你将探索golang的核心概念和高级技巧！
