Two Glass Balls and a Tower

Abstract

The bounded divide-and-conquer technique has been pioneered in Pattern Matching by Karl Abrahamson. Since its inception, the technique has proven useful in numerous results in combinatorial pattern matching and computational biology. Its wide use warrants a deeper study.

We will review and abstract the idea and show how it has aided in efficiently computing Hamming distance, less-than matching, masked maximum, and approximate weighted sequences matching.