字符串算法：编织文字的人

巴别图书馆

想象一座包含了字母所有可能组合的图书馆。在那无限的混乱中寻找一个特定的句子似乎是不可能的。 字符串算法就是这片混乱中的图书管理员。它们回答两个基本问题：

1. 搜索： “这本书里有‘爱’这个字吗？”
2. 压缩： “我能用更少的页数重写这本书而不丢失任何含义吗？”

在软件中，字符串无处不在。源代码、DNA 序列、HTTP 请求和用户日志本质上都是字符串。掌握字符串算法意味着掌握信息流本身。

模式的策略

在本章中，我们将探索处理文本的不同方式：

字符串的三大法则

1. 前缀 vs. 后缀： 大多数字符串魔法都发生在边缘。知道一个字符串如何开始（前缀）或如何结束（后缀），往往能告诉你关于中间部分的一切。
2. 状态机： 字符串算法通常只是一个在状态序列中移动的机器人。“我看到了一个 ‘H’，现在我在等一个 ‘E’…”
3. 字母表大小： 复杂度往往取决于字母表 ($\Sigma$) 的大小。搜索二进制 (0/1) 与搜索中文文本 (20,000+ 字符) 是不同的挑战。

小结

在本章中，我们将看到搜索引擎如何索引网络，以及 ZIP 文件如何将千兆字节压缩为兆字节。我们将明白，文本不仅仅是数据；它是一种等待被发现的结构。

让我们从最直观的结构开始：Trie 树。