除了 Knuth-Morris-Pratt、Rabin-Karp 等算法之外，还有哪些可用的字符串匹配算法？

Question

除了 Knuth-Morris-Pratt、Rabin-Karp 等算法之外，还有哪些可用的字符串匹配算法？

stringalgorithmpattern-matchingknuth-morris-prattrabin-karp

3

除了 Knuth-Morris-Pratt、Rabin-Karp 等算法之外，还有哪些可用的字符串匹配算法呢？

- BGV

3个回答

3

Simone Faro和Thierry Lecroq提供了一个C语言实现以及86种精确字符串匹配算法的参考资料，这些内容可以在"String Matching Algorithms Research Tool"中找到。

他们还提供了一个框架来对字符串匹配算法进行基准测试：

____________________________________________________________
Experimental results on englishTexts
Searching for a set of 200 patterns with length 128
Testing 5 algorithms

 - [1/5] BM ..................[OK]      0.88 ms       
 - [2/5] EPSM ................[OK]      0.38 ms       
 - [3/5] KMP .................[OK]      6.23 ms       
 - [4/5] KR ..................[OK]      1.84 ms       
 - [5/5] TW ..................[OK]      2.70 ms

算法

BM = Boyer-Moore算法（1977年）
EPSM = 精确打包字符串匹配算法（2013年）
KMP = Knuth-Morris-Pratt算法（1977年）
KR = Karp-Rabin算法（1987年）
TW = 双向算法（1991年）

- David L.

3

这个页面对许多算法进行了良好的简要描述：http://www-igm.univ-mlv.fr/~lecroq/string/index.html

- Jim Mischel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kvista · Accepted Answer

以下是包含在其中的算法：

可以在以下链接中找到这些算法的权威汇编：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距离等）也感兴趣的话，您可能需要澄清一下，因为它们是密切相关的。