string - Knuth-Morris-Pratt、Rabin-Karp などのほかに、利用可能な文字列マッチング アルゴリズムは何ですか?

Question

Knuth-Morris-Pratt、Rabin-Karp などのほかに、利用可能な文字列マッチング アルゴリズムは何ですか?

Answer 1

これらのアルゴリズムのよく引用されている概要は、次の場所にあります。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4896&rep=rep1&type=pdf

次のアルゴリズムが含まれます。

Karp-Rabin 
Shift Or 
Morris-Pratt 
Knuth-Morris-Pratt
Simon 
Colussi 
Galil-Giancarlo 
Apostolico-Crochemore
Not So Naive 
Forward Dawg Matching  
Boyer-Moore 
Turbo-BM 
Apostolico-Giancarlo 
Reverse Colussi 
Horspool 
Quick Search 
Tuned Boyer-Moore
Zhu-Takaoka 
Berry-Ravindran 
Smith 
Raita 
Reverse Factor 
Turbo Reverse Factor 
Backward Oracle Matching 

プラス約15人。

ところで、本当に興味がある場合は、密接に関連する文字列類似性アルゴリズム (レーベンシュタイン距離など) にも興味があるかどうかを明確にすることをお勧めします。

Answer 2

このページには、多くのアルゴリズムの簡単な説明があります: http://www-igm.univ-mlv.fr/~lecroq/string/index.html