第5章：字符串（Strings）
一、导读
1.1 本章学习目标
第5章介绍字符串处理的各种算法。字符串是计算机中最常见的数据类型，高效的字符串处理算法对于搜索引擎、编译器、生物信息学等领域至关重要。本章核心目标：
- 掌握字符串排序算法：LSD、MSD、三向快排
- 理解单词查找树（Trie）：前缀搜索的强大工具
- 掌握字符串匹配算法：KMP算法
- 了解正则表达式的实现：NFA和DFA
1.2 为什么本章如此重要
字符串处理是实际应用中最高频的需求之一。从简单的文本搜索到复杂的模式匹配，从自动补全到DNA序列分析，字符串算法无处不在。Trie树在搜索引擎的自动补全中广泛应用，KMP算法是字符串匹配的经典。
1.3 核心问题引导
字符串排序和普通排序有什么本质区别？
Trie树的空间复杂度是多少？如何优化？
KMP算法的核心思想是什么？为什么比朴素算法快？
正则表达式是如何工作的？NFA和DFA有什么区别？
二、核心概念详解
5.1 字符串排序
LSD（低位优先）字符串排序
适用于固定长度的字符串，从最右边的字符开始排序：
java
public class LSD {
public static void sort(String[] a, int W) {
int N = a.length;
int R = 256;
String[] aux = new String[N];
for (int d = W - 1; d >= 0; d--) {
int[] count = new int[R + 1];
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int r = 0; r < R; r++)
count[r + 1] += count[r];
for (int i = 0; i < N; i++)
aux[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)
a[i] = aux[i];
}
}
}MSD（高位优先）字符串排序
从最左边的字符开始，递归排序：
java
public class MSD {
private static int R = 256;
private static final int M = 15; // 小数组用插入排序
private static String[] aux;
public static void sort(String[] a) {
int N = a.length;
aux = new String[N];
sort(a, 0, N - 1, 0);
}
private static void sort(String[] a, int lo, int hi, int d) {
if (hi <= lo + M) {
Insertion.sort(a, lo, hi, d);
return;
}
int[] count = new int[R + 2];
for (int i = lo; i <= hi; i++) {
count[charAt(a[i], d) + 2]++;
}
for (int r = 0; r < R + 1; r++) {
count[r + 1] += count[r];
}
for (int i = lo; i <= hi; i++) {
aux[count[charAt(a[i], d) + 1]++] = a[i];
}
for (int i = lo; i <= hi; i++) {
a[i] = aux[i - lo];
}
for (int r = 0; r < R; r++) {
sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
}
}
private static int charAt(String s, int d) {
if (d < s.length()) return s.charAt(d);
else return -1;
}
}5.2 单词查找树（Trie）
java
public class TrieST<Value> {
private static final int R = 256;
private Node root;
private static class Node {
private Object val;
private Node[] next = new Node[R];
}
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null) return null;
return (Value) x.val;
}
private Node get(Node x, String key, int d) {
if (x == null) return null;
if (d == key.length()) return x;
char c = key.charAt(d);
return get(x.next[c], key, d + 1);
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d) {
if (x == null) x = new Node();
if (d == key.length()) {
x.val = val;
return x;
}
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, val, d + 1);
return x;
}
public Iterable<String> keys() {
return keysWithPrefix("");
}
public Iterable<String> keysWithPrefix(String prefix) {
Queue<String> queue = new LinkedList<>();
Node x = get(root, prefix, 0);
if (x == null) return queue;
collect(x, new StringBuilder(prefix), queue);
return queue;
}
private void collect(Node x, StringBuilder prefix, Queue<String> queue) {
if (x == null) return;
if (x.val != null) queue.add(prefix.toString());
for (char c = 0; c < R; c++) {
prefix.append(c);
collect(x.next[c], prefix, queue);
prefix.deleteCharAt(prefix.length() - 1);
}
}
public Iterable<String> keysThatMatch(String pattern) {
Queue<String> queue = new LinkedList<>();
collect(root, new StringBuilder(), pattern, queue);
return queue;
}
public String longestPrefixOf(String query) {
int length = search(root, query, 0, 0);
return query.substring(0, length);
}
private int search(Node x, String query, int d, int length) {
if (x == null) return length;
if (x.val != null) length = d;
if (d == query.length()) return length;
char c = query.charAt(d);
return search(x.next[c], query, d + 1, length);
}
}5.3 KMP字符串匹配
KMP算法通过预处理模式串，构建DFA（确定性有限自动机），实现线性时间的字符串匹配：
java
public class KMP {
private String pat;
private int[][] dfa;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
int R = 256;
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X]; // 复制不匹配情况
dfa[pat.charAt(j)][j] = j + 1; // 设置匹配情况
X = dfa[pat.charAt(j)][X]; // 更新重启状态
}
}
public int search(String txt) {
int i, j, N = txt.length(), M = pat.length();
for (i = 0, j = 0; i < N && j < M; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == M) return i - M; // 找到匹配
else return N; // 未找到
}
}分析：
- 构造DFA：O(RM)时间，O(RM)空间
- 匹配：O(N)时间，不需要回溯
5.4 正则表达式
正则表达式的匹配可以通过NFA（非确定性有限自动机）实现：
java
public class NFA {
private char[] re; // 正则表达式
private int M; // 状态数
private Digraph G; // epsilon转换图
public NFA(String regex) {
re = regex.toCharArray();
M = re.length;
G = new Digraph(M + 1);
Stack<Integer> ops = new Stack<>();
for (int i = 0; i < M; i++) {
int lp = i;
if (re[i] == '(' || re[i] == '|')
ops.push(i);
else if (re[i] == ')') {
int or = ops.pop();
if (re[or] == '|') {
lp = ops.pop();
G.addEdge(lp, or + 1);
G.addEdge(or, i);
} else if (re[or] == '(') {
lp = or;
}
}
if (i < M - 1 && re[i + 1] == '*') {
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
if (re[i] == '(' || re[i] == '*' || re[i] == ')')
G.addEdge(i, i + 1);
}
}
public boolean recognizes(String txt) {
// 使用NFA模拟匹配
// ...
return true; // 简化
}
}三、实战案例
3.1 自动补全系统
java
public class AutoComplete {
private TrieST<Integer> trie;
public AutoComplete() {
trie = new TrieST<>();
}
public void addWord(String word, int frequency) {
trie.put(word, frequency);
}
public List<String> suggest(String prefix, int maxResults) {
List<String> suggestions = new ArrayList<>();
for (String key : trie.keysWithPrefix(prefix)) {
suggestions.add(key);
if (suggestions.size() >= maxResults) break;
}
return suggestions;
}
public static void main(String[] args) {
AutoComplete ac = new AutoComplete();
ac.addWord("apple", 100);
ac.addWord("application", 80);
ac.addWord("apply", 60);
ac.addWord("banana", 40);
System.out.println(ac.suggest("app", 5));
// [apple, application, apply]
}
}3.2 文本搜索
java
public class TextSearch {
public static List<Integer> searchAll(String text, String pattern) {
List<Integer> positions = new ArrayList<>();
KMP kmp = new KMP(pattern);
int pos = 0;
while (pos < text.length()) {
int found = kmp.search(text.substring(pos));
if (found == text.length() - pos) break;
positions.add(pos + found);
pos += found + 1;
}
return positions;
}
public static void main(String[] args) {
String text = "ababcabcabc";
String pattern = "abc";
List<Integer> positions = searchAll(text, pattern);
System.out.println("Pattern found at: " + positions);
// [2, 5, 8]
}
}四、本章小结
第5章介绍了字符串算法：
字符串排序：LSD（固定长度，从右到左）、MSD（从左到右，递归）、三向快排。
Trie树：前缀搜索的核心数据结构，O(L)查找（L为键长），但空间开销大。
KMP算法：通过DFA实现线性时间匹配，不需要回溯。
正则表达式：通过NFA实现，支持复杂的模式匹配。
五、思考与练习
思考题
Trie树的空间复杂度是多少？如何优化（如压缩Trie）？
KMP算法的DFA如何构造？为什么不需要回溯？
NFA和DFA有什么区别？各自的优势是什么？
为什么字符串排序需要专门的算法？
编程练习
实现Trie树，支持插入、查找、前缀匹配、删除操作。
实现KMP算法，测试其在不同模式串上的性能。
使用Trie实现一个简单的拼写检查器。