RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2013 Volume 10, Pages 538–550 (Mi semr445)

Discrete mathematics and mathematical cybernetics

Two problems about recovering of damaged strings

M. V. Rubinchik, Yu. V. Gamzova

Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg

Abstract: We consider two problems related to pattern matching in damaged strings. In both problems, the goal is to recover the original undamaged text and pattern in an optimal way.
Problem 1. For given damaged text and damaged pattern, recover the text and the pattern in a way that maximizes the number of occurrences of the pattern in the text.
We define total Hamming distance between a text of length $n$ and a pattern of length $m$ to be the sum of Hamming distances for all pairs (pattern, factor of length $m$ of the text).
Problem 2. For given damaged text and damaged pattern, recover the text and the pattern in a way that minimizes the total Hamming distance between them.
We prove both problems to be $NP$-hard and provide efficient algorithms to various polynomially solvable subcases of these problems.

Keywords: damaged string, partial strings, pattern matching.

UDC: 519.16

MSC: 68W32

Received July 25, 2013, published September 3, 2013



© Steklov Math. Inst. of RAS, 2024