《算法》笔记：第5章 字符串
《算法》第5章：字符串。
字符串排序，单词查找树，字符串查找，正则表达式，数据压缩。
本章结构如下：
- 介绍字符串的基本性质。
- 字符串的排序和查找。
- 子字符串查找算法，包括Knuth、Morris和Pratt发明的一个著名的算法。
- 正则表达式，是模式匹配问题的基础。
- 重要应用：数据压缩，将字符串长度压缩到最小的程度。
5.1 字符串排序
两类完全不同的字符串排序方法：
- 低位优先的字符串排序，从右往左检查键中的字符，适用于键的长度都相同的字符串。
- 高位优先的字符串排序，从左到右检查键中的字符，它不一定需要检查所有的输入才能完成排序。
5.1.1 键索引计数法
适用于小整数键的排序，例如将学生姓名按照分组进行排序。
第一步，统计每个键出现的频率。
第二步，将键转化成索引，当前键索引的开始位置是之前键的总和。
第三步，数据分类，用一个辅助数组。
第四步，回写，将排序好的写回原数组。
5.1.2 低位优先的排序
低位优先的字符串排序算法能够稳定地将定长字符串排序。
就是一个基数排序。
5.1.3 高位优先的排序
高位优先的排序是一种递归算法。
类似基数排序，但是要注意字符串结束的情况。
5.1.4 三向字符串快速排序
三向字符串平均比较字符~2NlnN次。
5.2 单词查找树
由一棵多叉树保存。
5.3 子字符串查找
