String Algorithms字串演算法

在一億字的 log 裡找一段字串，暴力比對最壞是 O(nm)。KMP 利用「已經比對過的部分」不回頭，做到線性時間。

把每一段文字算成一個雜湊值，比對雜湊比比對文字快得多。Rabin-Karp 的滾動雜湊讓視窗移動時不用重算。

基因序列就是很長的 ACGT 字串。找特定片段、找回文結構（限制酶切位常是回文），都是字串演算法。

同時要在文件裡找幾千個關鍵字，字典樹把所有關鍵字疊在一起，掃一遍文件就全部找到。