除了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人.

顺便说一句,你可能想澄清你是否也对字符串相似性算法(例如Levenshtein距离等)感兴趣,这些算法密切相关,如果你确实对此感兴趣的话.