Efficient randomized pattern-matching algorithms
作者： Richard M. Karp , Michael O. Rabin
DOI: 10.1147/RD.312.0249
关键词: Bitap algorithm 、 Algorithm 、 Pattern matching 、 Rabin–Karp algorithm 、 String searching algorithm 、 Block (data storage) 、 Randomized algorithm 、 String (computer science) 、 Commentz-Walter algorithm 、 Mathematics
摘要: … We show that, in the case of Unear pattern matching or higher-dimensional array matching, the time for each ujxlate is bounded by a constant. It follows that, in these cases. Algorithm 1 …
acm.org
core.ac.uk
sci-hub.se 参考文章(11)
Joel I. Seiferas, Zvi Galil, Zvi Galil, Time-Space-Optimal String Matching symposium on the theory of computing. pp. 106- 113 ,(1981)
J. Barkley Rosser, Lowell Schoenfeld, Approximate formulas for some functions of prime numbers Illinois Journal of Mathematics. ,vol. 6, pp. 64- 94 ,(1962) , 10.1215/IJM/1255631807
R. Solovay, V. Strassen, A Fast Monte-Carlo Test for Primality SIAM Journal on Computing. ,vol. 6, pp. 84- 85 ,(1977) , 10.1137/0206006
Uzi Vishkin, Optimal Parallel Pattern Matching in Strings ,(2011)
R.S. Bird, Two dimensional pattern matching Information Processing Letters. ,vol. 6, pp. 168- 170 ,(1977) , 10.1016/0020-0190(77)90017-5
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
Michael O Rabin, Probabilistic algorithm for testing primality Journal of Number Theory. ,vol. 12, pp. 128- 138 ,(1980) , 10.1016/0022-314X(80)90084-0
Zvi Galil, Joel Seiferas, Time-space-optimal string matching (Preliminary Report) Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 106- 113 ,(1981) , 10.1145/800076.802463
Zvi Galil, Joel Seiferas, Saving Space in Fast String-Matching SIAM Journal on Computing. ,vol. 9, pp. 417- 438 ,(1980) , 10.1137/0209032
Robert S. Boyer, J. Strother Moore, A fast string searching algorithm Communications of the ACM. ,vol. 20, pp. 762- 772 ,(1977) , 10.1145/359842.359859