Pattern Matching with Non Overlapping Reversals - Approximation and On-line Algorithms

The

Sorting by Reversals

Problem is known to be

$\cal{NP}$

-hard. A simplification,

Sorting by Signed Reversals

is polynomially computable. Motivated by the Pattern Matching with Rearrangements model, we consider

Pattern Matching with Reversals

. Since this is a generalization of the Sorting by Reversals problem, it is clearly

${\cal NP}$

-hard. We, therefore consider the simplification where reversals cannot overlap. Such a constrained version has been researched in the past for various metrics in the rearrangement model - the swap metric and the interchange metric. We show that the constrained problem can be solved in linear time. We then consider the

Approximate Pattern Matching with non-overlapping Reversals

problem, i.e. where mismatch errors are introduced. We show that the problem can be solved in quadratic time and space. Finally, we consider the on-line version of the problem. We introduce a novel signature for palindromes and show that it has a pleasing behavior, similar to the Karp-Rabin signature. It allows solving the

Pattern Matching with non-overlapping Reversals

problem on-line in linear time w.h.p.