Approximate Online Pattern Matching in Sub-linear Time

Diptarka Chakraborty, Debarati Das, Michal Koucky

We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern $P$ of length $w$ and a text $T$ of length $n$ over some alphabet $…