Rabin-Karp演算法

方法

1. 計算匹配字串的hash value
2. 計算文本的子字串的hash value

採用前一次子字串的hash value來降低運算次數， 減去開頭字元的hash value並加上新字元的hash valuse。

實作

可能的資料結構

• 佇列: 直接使用輸入文本，並記錄匹配結尾與匹配開頭。
• hash function: 採用一個大質數來減少碰撞機率，將字元編碼相加。

範例程式參見GitHub

---

String Searching Algorithm Hash