處理字串匹配的演算法

• Knuth-Morris-Pratt (KMP) 演算法 KMP 演算法透過避免重新檢查已知不匹配的字元來提高效率。 它使用一個部分匹配表來記錄 needle 字串中的模式，這樣當發現不匹配時，演算法可以直接跳過先前已經確定不匹配的部分。 這意味著在最壞的情況下，KMP 演算法的時間複雜度為 O(n)，其中 n 是 haystack 的長度。

• Boyer-Moore 演算法 Boyer-Moore 演算法是一種更高級的字串匹配演算法，其效能通常優於 KMP。 它從右向左比較字符，利用不匹配字符的信息來跳過一些不可能的匹配位置。 這種「跳過」策略使得它在實際應用中往往比 KMP 更快，尤其是當匹配的模式較長時。

• Rabin-Karp 算法 Rabin-Karp 演算法使用雜湊函數來偵測候選字串是否與目標字串匹配，這使得它在某些情況下能夠快速地排除大量不匹配的情況。 它特別適合在單一文字中尋找多個模式或在大型文字中尋找模式的情況。