A Simple Fast Hybrid Pattern-Matching Algorithm
作者： Frantisek Franek , Christopher G. Jennings , William F. Smyth
DOI: 10.1007/11496656_25
关键词: Time complexity 、 Computer science 、 Simple (abstract algebra) 、 Independence (probability theory) 、 Algorithm 、 Pattern recognition (psychology) 、 String searching algorithm 、 Execution time 、 Pattern matching
摘要: The Knuth-Morris-Pratt (KMP) pattern-matching algorithm guarantees both independence from alphabet size and worst-case execution time linear in the pattern length; on other hand, Boyer-Moore (BM) provides near-optimal average-case best-case behaviour, as well executing very fast practice. We describe a simple that employs main ideas of KMP BM (with little help Sunday) an effort to combine these desirable features. Experiments indicate practice new is among fastest exact algorithms discovered date, perhaps dominant for 8 or more.
springer.com
core.ac.uk
murdoch.edu.au参考文章(22)
Gonzalo Navarro, Mathieu Raffinot, A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching combinatorial pattern matching. pp. 14- 33 ,(1998) , 10.1007/BFB0030778
Daniel M. Sunday, A very fast substring search algorithm Communications of the ACM. ,vol. 33, pp. 132- 142 ,(1990) , 10.1145/79173.79184
Zvi Galil, On improving the worst case running time of the Boyer-Moore string matching algorithm Communications of the ACM. ,vol. 22, pp. 505- 508 ,(1979) , 10.1145/359146.359148
Andrew Hume, Daniel Sunday, Fast string searching Software - Practice and Experience. ,vol. 21, pp. 1221- 1248 ,(1991) , 10.1002/SPE.4380211105
Ricardo Baeza-Yates, Gaston H. Gonnet, A new approach to text searching Communications of The ACM. ,vol. 35, pp. 74- 82 ,(1992) , 10.1145/135239.135243
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
R. Nigel Horspool, Practical Fast Searching in Strings Software - Practice and Experience. ,vol. 10, pp. 501- 506 ,(1980) , 10.1002/SPE.4380100608
Zvi Galil, Raffaele Giancarlo, On the exact complexity of string matching: lower bounds SIAM Journal on Computing. ,vol. 20, pp. 1008- 1020 ,(1991) , 10.1137/0220063
L. Colussi, Fastest pattern matching in strings Journal of Algorithms. ,vol. 16, pp. 163- 189 ,(1994) , 10.1006/JAGM.1994.1008
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski, W. Rytter, Speeding up two string-matching algorithms Algorithmica. ,vol. 12, pp. 247- 267 ,(1994) , 10.1007/BF01185427