String Matching with Inversions and Translocations in Linear Average Time (Most of the Time)

Szymon Grabowski, Simone Faro, Emanuele Giaquinta

We present an efficient algorithm for finding all approximate occurrences of a given pattern $p$ of length $m$ in a text $t$ of length $n$ allowing for translocations of equal leng…