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

Given an alphabet Sigma = {1, 2,..., vertical bar Sigma vertical bar} text string T is an element of Sigma(n) and a pattern string P is an element of Sigma(m), for each i = 1, 2,..., n-m + 1 define L-d(i) as the d-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern snatching 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, infinity. First; in the case of L-1 matching (pattern snatching with an L-1 distance) we present an algorithm that approximates the L, snatching up to a factor of 1 + epsilon, which has an O(1/epsilon(2) n log mlog vertical bar Sigma vertical bar) run time. Second, we provide all algorithm that approximates the L. snatching up to a factor of 1 + epsilon with a run time of O(1/epsilon n log mlog vertical bar Sigma vertical bar). We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(n log(4) m) algorithm that approximates the results of this problem lip to a factor of O(log m) in the case that the weight function is a metric.