字串匹配-Multiple pattern search
Rabin-Karp 演算法
如果今天您要實作一個聊天室的訊息過濾器，您會如何實作？
共 N 個敏感詞彙，每個敏感詞彙的平均長度為 M，每個句子包含 K 個字元。
Q1. 使用何種資料結構？ 所需空間複雜度為何？
Q2. 使用何種方式過濾？ 所需時間複雜度為何？
Q3. 使用何種方式進行測試？
Q4. 在運作期間要更新詞彙列表的話要如何處理？
Q1. 使用何種資料結構？ 所需空間複雜度為何？
如果要求一定要正確抓出敏感詞彙，有就有，沒有就沒有，資料結構使用hash table。
空間複雜度:O(N)不是敏感詞彙，卻顯示是敏感詞彙，心態是寧可錯殺不可放過，如果允許這樣的誤報，
那麼資料結構使用Bloom Filter的變體，也就是Cuckoo Filter。
空間複雜度:O(1)
Q2. 使用何種方式過濾？ 所需時間複雜度為何？
首先對所有的敏感詞彙做前置處理，將敏感詞彙輸入到hash函數，所得到的hash值儲存到 hash table 或 Cuckoo Filter。
其中hash函數的設計與字串長度有關，時間複雜度為O(M)，而現在有N個敏感詞彙，故前置處理階段的時間複雜度為O(NM)。
匹配運算中， 第14行計算子字串的hash值，hash函數與字串長度有關，其時間複雜度為O(M)，為了減少這部分的時間複雜度，利用rolling hash的技巧，由於每個子字串與下一個子字串有高度的重複性，利用這樣的特性，目前子字串的hash值=前一個子字串的hash值-前一個字元的hash值+新出現字元的hash值，藉由這樣的方式就不需要每次迴圈都計算子字串中的M個字元，只需要考慮頭尾字元所造成的影響，第14行的時間複雜度變為O(1)。
第12行，查詢子字串的hash值是否存在於敏感詞彙hash值的集合hsSet，由於hsSet 是以hash table的方式儲存，第12行的時間複雜度為O(1)，但即使hash值相等還是要考慮到碰撞的情況產生，因此需要依序對比字串，時間複雜度為O(1*M)。
若是在很倒楣的情況，比如說不斷出現重複的字元，那麼每次都會發生hash碰撞，匹配運算的最糟時間複雜度為O((K-M)M)，但正常情況hash碰撞的情況很少發生， 其時間複雜度為O((K-M) + cM) = O(K+M)。
Q3. 使用何種方式進行測試？
1.以array儲存預設要輸入的訊息，依序輸入，判斷輸出是否符合預期
2.建構隨機字串，依序輸入，判斷輸出是否符合預期
Q4. 在運作期間要更新詞彙列表的話要如何處理？
更新詞彙列表對運作中的訊息過濾器不會有影響，理由有兩個:
- 函數是用by value傳遞敏感詞彙，因此外部更新詞彙列表也不會有影響
- 在前置處理階段已經確定了敏感詞彙的hash值，匹配過程中，即使更新詞彙列表，也不會影響已經計算過了敏感詞彙的hash值
假設更新詞彙列表只增加不會減少，畢竟不是戒嚴時期，敏感詞彙應該不會減少只會增加，那麼就將更新前過濾的文章，輸入新的敏感詞彙，再次做一次過濾動作，不需要對舊的敏感詞彙做過濾
結語:
Rabin–Karp在 single pattern的情況下並不是好的選擇，但是在Multiple pattern有不錯的效果。
