字串演算法 (String Algorithms)

字串比對、搜尋與處理的演算法

字串比對

暴力比對：逐位元比較，時間 O(nm)。

KMP 演算法：利用前綴函數避免重複比對，時間 O(n+m)。

Rabin-Karp：使用雜湊進行快速比對，平均 O(n+m)。

Boyer-Moore：從右向左比對，利用壞字元和好後綴規則跳過無用比較。

最長公共子序列 (LCS)：DP 方法，時間 O(nm)。

最長遞增子序列 (LIS)：O(n log n) 最佳化解法。

編輯距離 (Levenshtein)：計算兩個字串的最小編輯操作次數。

Trie 是一種樹狀資料結構，用於高效儲存和查找字串集合。每個節點代表一個前綴，路徑上的字元組成字串。常用於自動補全、拼寫檢查、IP 路由。