字串幾乎出現在每一場競賽程式設計比賽中，但它絆倒的學生比任何其他主題都多，因為逐個字元比較的樸素解法往往慢得離譜。
當一道題要求你在一段長文本中尋找模式、統計重複子字串或偵測回文時，暴力解法的時間複雜度可能膨脹到 O(n*m)，在大規模輸入下超出限制。好消息是，一套精煉且易於理解的競賽程式設計字串演算法工具箱就能涵蓋絕大多數這類任務。一旦你辨識出其中的模式，正確的技術便會一目了然。本指南將帶你逐一了解這套工具箱，以及有志的學生該如何為 USACO 等比賽掌握它們。
必須掌握的核心字串演算法
你並不需要幾十種技術。深入掌握少數幾個可靠的工具，就能讓你走得很遠：
- 字串雜湊（Rabin-Karp） — 使用滾動雜湊以近乎常數的時間把子字串當作數字來比較。它與二分搜尋配合得天衣無縫，適用於尋找最長重複子字串或最長共同子字串等任務。選擇合適的底數和較大的模數以避免碰撞。
- KMP（Knuth-Morris-Pratt） — 建構一個前綴函式（即 LPS 陣列），使模式字串永遠不會重新掃描已經經過的文本，從而實現確定性的 O(n + m) 匹配。它非常適合串流輸入，以及當你想規避雜湊碰撞這一微小風險的情境。
- Z 演算法 — 為每個位置計算從該處出發、與字串前綴相匹配的最長子字串長度。把模式字串 + 分隔符 + 文本串接起來，就能將其轉化為乾淨的線性時間模式匹配，並能優雅地處理重疊匹配。
- 字典樹（Trie） — 一種透過共享前綴來儲存大量字串的樹，可實現快速查找、自動完成式查詢以及位元 XOR 類問題的求解。
- Manacher 演算法 — 以線性時間找出以每個位置為中心的最長回文，取代緩慢的回文偵測。
對於更難的問題，後綴陣列（通常配合 LCP 陣列）以及用於一次性匹配多個模式的 Aho-Corasick 自動機變得不可或缺。這些屬於進階內容，因此請等到基礎扎實後再學習。
選擇合適的工具
把演算法與問題對應起來，成功就已經一半了。這裡有幾條快速的經驗法則：
- 在單個文本中尋找單個模式？KMP 和 Z 演算法都以線性時間執行。挑你寫得最有把握的那個。
- 比較大量子字串，或需要最長共同／重複子字串？雜湊配合二分搜尋通常是最簡潔的路徑。
- 同時搜尋多個模式？在字典樹之上建構 Aho-Corasick 自動機。
- 回文密集型問題？選用 Manacher 演算法或回文樹。
- 子字串排序、相異子字串計數或後綴比較？帶 LCP 的後綴陣列是主力工具。
這如何對應到 USACO 等比賽
USA Computing Olympiad 每個賽季舉辦四場比賽，每場三道題，依據隱藏測試案例評分，並分為四個組別：Bronze、Silver、Gold 和 Platinum。每位新參賽者都從 Bronze 開始，達到每場比賽的晉級分數線即可晉級。字串題目出現在每個級別：Bronze 和 Silver 的題目倚重細緻的操作和簡單的匹配，而 Gold 和 Platinum 則可能要求後綴陣列、Z 演算法或 Aho-Corasick。由於規則和晉級細節會隨賽季變化，請始終在 USACO 官方網站上確認當前的賽制和參賽資格，而不要依賴任何單一的指南。
先掌握線性時間的匹配演算法；按每小時學習投入來算，它們解鎖的題目比任何高階資料結構都多。
一份行之有效的學習計畫
一次只學一個演算法，並從零開始把它實作出來，然後只用那一個工具解五到十道題，直到它變成本能。保留一份你信賴的個人範本檔案。一週之後重溫每個主題，以對抗遺忘。在經驗豐富的教練回饋下進行有結構的練習，會極大地加速這一過程，這正是有引導的路徑往往勝過單打獨鬥的原因。
相比純粹的靈光一現，字串演算法更看重模式辨識和乾淨的實作，這使它們成為穩步、可衡量進步的絕佳領域。如果你想要一條從基礎到 Platinum 級技術的有結構路徑，歡迎了解 BIAA 的競賽程式設計課程，在我們的部落格上瀏覽更多學習指南，或今天就從 BIAA 首頁開始。