Faster Approximate Pattern Matching: A Unified Approach
Faster Approximate Pattern Matching: A Unified Approach
In the approximate pattern matching problem, given a text T, a pattern P, and a threshold k, the task is to find (the starting positions of) all substrings of T that are at distance at most k from P. We consider the two most fundamental string metrics: Under the Hamming …