Geodesic
Two problems about recovering of damaged strings
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 10 (2013), pp. 538-550

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2013_10_a37,
     author = {M. V. Rubinchik and Yu. V. Gamzova},
     title = {Two problems about recovering of damaged strings},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {538--550},
     publisher = {mathdoc},
     volume = {10},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2013_10_a37/}
}
TY  - JOUR
AU  - M. V. Rubinchik
AU  - Yu. V. Gamzova
TI  - Two problems about recovering of damaged strings
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2013
SP  - 538
EP  - 550
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2013_10_a37/
LA  - ru
ID  - SEMR_2013_10_a37
ER  - 
%0 Journal Article
%A M. V. Rubinchik
%A Yu. V. Gamzova
%T Two problems about recovering of damaged strings
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2013
%P 538-550
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2013_10_a37/
%G ru
%F SEMR_2013_10_a37
M. V. Rubinchik; Yu. V. Gamzova. Two problems about recovering of damaged strings. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 10 (2013), pp. 538-550. http://geodesic.mathdoc.fr/item/SEMR_2013_10_a37/