字符串处理

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

先理解 string 的字节下标与 rune；每个 package main 代码块是独立 main.go，不能合并同目录。可在新模块中单独保存一个例子（Go 1.22+，滚动哈希需 64 位 int）。下文输出均为静态推导，本轮未运行；空模式在三种查找中返回 0，未找到返回 -1。

要解决的问题	可选方法	选择前确认
归类由相同字符组成的词或提取共同开头	变位词分组或最长公共前缀	两例都用 rune；分组排序键与跨单词比较前缀是不同任务。
短文本中查找一个模式	朴素字符串匹配	无需预处理，最坏 O(nm)；示例返回 UTF-8 字节下标。
避免重复前缀导致反复比较	KMP	前缀函数跳过已知匹配，时间 O(n+m)；示例使用字节下标。
需要每个位置与整串前缀的匹配长度	Z 算法	时间 O(n)；拼接模式、分隔符和文本也可查找匹配。
滑动比较定长窗口	滚动哈希与Rabin–Karp	哈希相同不代表原文相同；Rabin–Karp 会二次比对，最坏性能仍可能退化。
按符号频率降低加权路径代价	哈夫曼编码	示例只计算总代价；生成实际 0/1 编码还需保存树结构。

按字符组成分组与提取公共前缀

变位词分组

正文、推演与完整示例：变位词分组。

排序每个长度为 m 的词需要 O(m log m)；固定小字符集也可用计数向量作键。

最长公共前缀

正文、推演与完整示例：最长公共前缀。

示例按 rune 比较，不会把中文字符截成无效的 UTF-8 字节片段。

从逐项比对到复用前缀匹配结果

朴素字符串匹配

正文、推演与完整示例：朴素字符串匹配。

这个 Go 例子按 UTF-8 字节查找并返回字节下标。

KMP 字符串匹配

正文、推演与完整示例：KMP 字符串匹配。

本例 KMP 按 UTF-8 字节匹配，因此中文也必须比较每个续字节，不能用 range string 跳过它们。pattern 是模式串；KMP("你好Go", "Go") 返回字节下标 6，查找“好”返回 3，均不表示第几个 rune。空模式返回 0，没有匹配返回 -1。

预处理和搜索各为线性时间；示例返回字节下标。

Z 算法

正文、推演与完整示例：Z 算法。

把“模式＋分隔符＋文本”拼接后，也能用 Z 值寻找所有匹配位置。

用滚动哈希筛选窗口并核对匹配

滚动哈希

正文、推演与完整示例：滚动哈希。

模哈希会碰撞，因此需要精确相等时必须二次比较原文；双哈希只能降低碰撞概率，不能证明相等。本页哈希算式使用 int，中间乘积要求 64 位 int；32 位目标应先改为 int64。

Rabin–Karp

正文、推演与完整示例：Rabin–Karp。

平均性能良好，但恶意碰撞可能让最坏时间退化。

按频率计算哈夫曼合并代价

哈夫曼编码

正文、推演与完整示例：哈夫曼编码。

反复排序便于理解，使用最小堆可更高效。

静态自检

预测 KMP("你好Go", "Go") 与 KMP("你好Go", "好") 的字节下标。提示：两个汉字分别占三个 UTF-8 字节，查找循环必须检查每个字节。

参考解法

分别为 6 和 3；若按 range string 只遍历码点起点，比较好字的首字节后会跳过其续字节而漏报。当前循环逐字节处理，匹配结果仍是字节下标。