Approximate Pattern Matching with the L1, L2 and L∞ Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σn and a pattern string P∈Σm, for each i=1,2,…,n−m+1 define Lp(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 Lp distance is to compute Lp(i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L1 matching (pattern matching with an L1 distance) we show a reduction of the string matching with mismatches problem to the L1 matching problem and we present an algorithm that approximates the L1 matching up to a factor of 1+ε, which has an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|)$\end{document} run time. Then, the L2 matching problem (pattern matching with an L2 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\frac{1}{\varepsilon}n\log m\log|\Sigma|)$\end{document} . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog 4m) 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.