字符串算法处理的是符号序列，首先要说明“一个字符”指什么。Python str 按Unicode码点索引，不按UTF-8字节索引，也不保证一个下标就是屏幕上的一个完整字形。组合音标、表情组合和大小写折叠都可能改变比较与位置的含义。
朴素匹配重复了什么
在文本每个位置尝试匹配模式，最坏要比较 O(nm) 次。模式包含重复前缀时，某次失败之前的比较结果其实提供了下一次尝试的信息。KMP把这些信息预先编码到模式的前缀表中。
prefix[i] 表示模式前缀 pattern[:i+1] 的最长真前后缀长度。“真”表示不能等于整段本身。例如 abab 的最长真前后缀是 ab，长度2。匹配已经完成 j 个字符却失败时，只有已经匹配部分的后缀还能作为下一次的前缀，因此令 j=prefix[j-1] 继续尝试，无须把文本指针退回去。
def prefix_table(pattern):
table = [0] * len(pattern)
matched = 0
for i in range(1, len(pattern)):
while matched and pattern[i] != pattern[matched]:
matched = table[matched - 1]
if pattern[i] == pattern[matched]:
matched += 1
table[i] = matched
return table
def find_all(text, pattern):
if not pattern:
return list(range(len(text) + 1))
table = prefix_table(pattern)
matched, positions = 0, []
for i, char in enumerate(text):
while matched and char != pattern[matched]:
matched = table[matched - 1]
if char == pattern[matched]:
matched += 1
if matched == len(pattern):
positions.append(i - len(pattern) + 1)
matched = table[matched - 1]
return positions
if __name__ == '__main__':
print(find_all('ababa', 'aba'))
find_all('ababa','aba') 返回 [0,2]，保留重叠匹配。找到一次完整匹配后也退到最长真前后缀，而非直接清零。空模式约定在每个字符间隙都匹配，因此返回 0..n；如果产品不允许空查询，应在入口拒绝，而不是让底层函数含糊处理。
文本指针只向前，模式指针增加次数受扫描次数约束，失败回退总次数也受增加次数限制；前缀表与匹配阶段都是线性，所以时间 O(n+m)，除输出外空间 O(m)。结果数量最多为n+1，保存全部结果的成本也应计入。
Trie与滚动哈希
Trie把单词前缀共享成树，沿查询字符串逐字符前进。查一个长度L的键，若孩子映射平均常数时间，成本 O(L)；枚举补全结果还要加输出大小。大量稀疏孩子会产生对象开销，压缩路径或排序数组可能更合适。它适合字典前缀查询，不会自动解决任意子串检索。
滚动哈希用一个固定长度窗口的摘要推导下个窗口摘要，便于比较候选子串。哈希相等仍可能碰撞，若要求完全正确，就要核对原字符；核对次数很多时最坏成本可能退化。双哈希降低概率，也不能把概率结论写成无碰撞证明。
压缩中的哈夫曼树则生成前缀码，使任何码字都不是其他码字前缀，解码时能确定边界。在给定符号频率和逐符号前缀码模型下，贪心合并最小频率节点有最优性；模型改变后不能拿这个结论代替所有压缩算法的比较。
规范化与位置映射
é 可以表示为一个预组码点，也可以表示为 e 加组合音标。若希望它们视为相等，可在检索入口统一Unicode规范化，但规范化后得到的位置不一定能直接当作原文下标。高亮结果需保留映射，或明确只对规范化后的文本操作。示例按原始码点精确匹配。
练习与面试自查
用朴素切片匹配作为小规模基线，生成大量重复字符和随机文本对拍。加入中文、组合字符、空模式、模式长于文本和重叠命中。再实现Trie的插入、精确查找和前缀查询，区别“路径存在”与“路径终点是一个单词”。
面试中应能画出失配时可复用的边界，说明为什么文本指针不用回退，以及哈希相等为什么仍需要核验。把码点、字节与字形混为一谈会在实际搜索高亮中造成错误。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。