查看文章

Approximate matching is one of the fundamental problems in pattern matching, and a ubiquitous problem in real applications. The Hamming distance is a simple and well studied example of approximate matching, motivated by typing, or noisy channels. Biological and image processing applications assign a different value to mismatches of different symbols.

We consider the problem of approximate matching in the L ₁ metric – the k- L ₁ -distance problem. Given text T=t ₀,...,t _n − 1 and pattern P=p ₀,...,p _m − 1 strings of natural number, and a natural number k, we seek all text locations i where the L ₁ distance of the pattern from the length m substring of text starting at i is not greater than k, i.e. .

We provide an algorithm that solves the k-L …