caa a22 4500 445804602 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9345-9 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9345-9 Approximate Pattern Matching with the L 1, L 2 and L ∞ Metrics [Elektronische Daten] [Ohad Lipsky, Ely Porat] Given an alphabet Σ={1,2, ,|Σ|} text string T∈Σn and a pattern string P∈Σm, for each i=1,2, ,n−m+1 define L p(i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L p distance is to compute L p(i) for every i=1,2, ,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L 1 matching (pattern matching with an L 1 distance) we show a reduction of the string matching with mismatches problem to the L 1 matching problem and we present an algorithm that approximates the L 1 matching up to a factor of 1+ε, which has an $O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|)$ run time. Then, the L 2 matching problem (pattern matching with an L 2 distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L ∞ matching up to a factor of 1+ε with a run time of $O(\frac{1}{\varepsilon}n\log m\log|\Sigma|)$ . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog 4 m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric. Springer Science+Business Media, LLC, 2009 Design and analysis of algorithms nationallicence Combinatorial algorithms on words nationallicence Approximate string matching nationallicence Hamming distance nationallicence Lipsky Ohad Department of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel aut Porat Ely Department of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel aut Algorithmica Springer-Verlag 60/2(2011-06-01), 335-348 0178-4617 60:2<335 2011 60 453 https://doi.org/10.1007/s00453-009-9345-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9345-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Lipsky Ohad Department of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel aut NATIONALLICENCE 700 1- Porat Ely Department of Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 335-348 0178-4617 60:2<335 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer