Efficient String Matching With K Mismatches
作者： U Vishkin , G M Landau
DOI:
关键词:
摘要: Abstract Given a text of length n , pattern m and an integer k we present algorithm for finding all occurrences the in text, each with at most mismatches. The runs O( ( log + )) time.
core.ac.uk
acm.org
amazon.com
openlibrary.org参考文章(7)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Richard M. Karp, Michael O. Rabin, Efficient randomized pattern-matching algorithms Ibm Journal of Research and Development. ,vol. 31, pp. 249- 260 ,(1987) , 10.1147/RD.312.0249
Zvi Galil, Joel Seiferas, Time-space-optimal string matching Journal of Computer and System Sciences. ,vol. 26, pp. 280- 294 ,(1983) , 10.1016/0022-0000(83)90002-8
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
Zvi Galil*, Optimal parallel algorithms for string matching symposium on the theory of computing. pp. 240- 248 ,(1984) , 10.1145/800057.808687
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
Uzi Vishkin, Optimal parallel pattern matching in strings international colloquium on automata, languages and programming. pp. 497- 508 ,(1985) , 10.1007/BFB0015775