除了Knuth-Morris-Pratt，Rabin-Karp和likes of it之外，还有什么可用的字符串匹配算法？
除了Knuth-Morris-Pratt，Rabin-Karp和likes of it之外，还有什么可用的字符串匹配算法？
提问于 2011-02-24 23:18:32
除了Knuth-Morris-Pratt，Rabin-Karp和likes of it之外，还有什么可用的字符串匹配算法？
回答 3
Stack Overflow用户
发布于 2011-02-24 23:25:01
这些算法的一个很好的引用概要可以在：
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距离等)，它们是密切相关的。
Stack Overflow用户
发布于 2011-02-25 00:20:49
这个页面有很多算法的简短描述：http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Stack Overflow用户
发布于 2013-05-12 23:04:10
Simone Faro和Thierry在"String Matching Algorithms Research Tool"上提供了一个C实现和对86个精确字符串匹配算法的参考。
它们还提供了一个对字符串匹配算法进行基准测试的框架：
____________________________________________________________
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)
<代码>H113TW=双向(1991)<代码>H214<代码>F215
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5106586
复制相关文章
相似问题
腾讯云开发者
