Faster ED-String Matching with $k$ Mismatches

Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak +2

We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of $n$ finite sets of strings of total length $N$, and compac…