除了 Knuth-Morris-Pratt、Rabin-Karp 等，还有哪些可用的字符串匹配算法？
问问题
1776 次
3 回答
8
这些算法的一个被广泛引用的纲要可以在以下位置找到：
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 距离等）感兴趣。
于 2011-02-24T15:25:01.340 回答
3
Simone Faro 和 Thierry Lecroq 在 “字符串匹配算法研究工具”上提供了一个 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 = 博耶摩尔 (1977)
- EPSM = 精确压缩字符串匹配算法 (2013)
- KMP = Knuth Morris-Pratt (1977)
- KR = 卡普·拉宾 (1987)
- TW = 两路 (1991)
于 2013-05-12T15:04:09.900 回答
3
该页面对许多算法有很好的简要描述：http ://www-igm.univ-mlv.fr/~lecroq/string/index.html
于 2011-02-24T16:20:49.390 回答