Approximate Matching in the L ∞ Metric

Let a text T=t 0,...,t n − − 1 and a pattern P=p 0,..., p m − − 1, strings of natural numbers, be given. In the Approximate Matching in the L  ∞  metric problem the output is, for every text location i, the L  ∞  distance between the pattern and the length m substring of the text starting at i, i.e. Max j=0m-1_{j=0}^{m--1}|t i+j_{i+{\it j}}–p j |. We consider the Approximate k –L  ∞  distance problem. Given text T and pattern P as before, and a natural number k the output of the problem is the L  ∞  distance of the pattern from the text only at locations i in the text where the distance is bounded by k. For the locations where the distance exceeds k the output is φ. We show an algorithm that solves this problem in O(n(k + log(min(m, |Σ|)))logm) time.