Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems

Raphael Clifford, Markus Jalsenius, Benjamin Sach

We give cell-probe bounds for the computation of edit distance, Hamming distance, convolution and longest common subsequence in a stream. In this model, a fixed string of $n$ symbo…