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/

[1] M. Fischer, M. Paterson, “String matching and other products”, SIAM-AMS Proceedings, 7, 1974, 113–125 | MR

[2] D. Gusfield, Algorithm on Strings, Trees, and Sequences, Cambridge University press, 1997 | MR | Zbl

[3] S. Muthukrishnan, H. Ramesh, “String matching under a general matching relation”, Proc. 12th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, 652, Springer-Verlag, Berlin, 1992, 356–367 | DOI | MR

[4] Knut D., Iskusstvo programmirovaniya, v. 2, Poluchislennye algoritmy, Vilyams, M., 2007

[5] S. Muthukrishnan, K. Palem, “Non-standard stringology: algorithms and complexity”, Proc. 26th Annual ACM Symposium on Theory of Computing, STOC'94, ACM, New York, 1994, 770–779

[6] Ge Nong, Sen Zhang, Wai Hong Chan, “Linear Time Suffix Array Construction Using D-Critical Substrings”, Lecture Notes in Computer Science, 5577, 2009, 54–67 | DOI | Zbl

[7] D. E. Knuth, J. H. Morris (Jr.), V. R. Pratt, “Fast Pattern Matching in Strings”, SIAM J. Comput., 6:2 (1977), 323–350 | DOI | MR | Zbl

[8] T. Kärki, T. Harju, V. Halava, “Interaction Properties of Relational Periods”, Discrete Mathematics Theoretical Computer Science, 10:1 (2008), 87–111 | MR

[9] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis, “The Complexity of Multiterminal Cuts”, SIAM J. Comput., 23 (1994), 864–894 | DOI | MR | Zbl