字串演算法：編織文字的人

巴別圖書館

想像一座包含了字母所有可能組合的圖書館。在那無限的混亂中尋找一個特定的句子似乎是不可能的。 字串演算法就是這片混亂中的圖書管理員。她們回答兩個基本問題：

1. 搜尋： 「這本書裡有『愛』這個字嗎？」
2. 壓縮： 「我能用更少的頁數重寫這本書而不丟失任何含義嗎？」

在軟體中，字串無處不在。原始碼、DNA 序列、HTTP 請求和用戶日誌本質上都是字串。掌握字串演算法意味著掌握資訊流本身。

模式的策略

在本章中，我們將探索處理文本的不同方式：

字串的三大法則

1. 前綴 vs. 後綴： 大多數字串魔法都發生在邊緣。知道一個字串如何開始（前綴）或如何結束（後綴），往往能告訴妳關於中間部分的一切。
2. 狀態機： 字串演算法通常只是一個在狀態序列中移動的機器人。「我看到了一個 ‘H’，現在我在等一個 ‘E’…」
3. 字母表大小： 複雜度往往取決於字母表 ($\Sigma$) 的大小。搜尋二進位 (0/1) 與搜尋中文文本 (20,000+ 字元) 是不同的挑戰。

小結

在本章中，我們將看到搜尋引擎如何索引網絡，以及 ZIP 檔案如何將千兆字節壓縮為兆字節。我們將明白，文本不僅僅是數據；她是一種等待被發現的結構。

讓我們從最直觀的結構開始：Trie 樹。