Geodesic
Faster subsequence recognition in compressed strings
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 282-300

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

Computation on compressed strings is one of the key approaches to processing massive data sets. We consider local subsequence recognition problems on strings compressed by straight-line programs (SLP), which is closely related to Lempel–Ziv compression. For an SLP-compressed text of length $\overline m$, and an uncompressed pattern of length $n$, Cégielski et al. gave an algorithm for local subsequence recognition running in time $O(\overline mn^2\log n)$. We improve the running time to $O(\overline mn^{1.5})$. Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time $O(\overline mn^{1.5})$; the same problem with a compressed pattern is known to be NP-hard. Bibl. – 22 titles. 
@article{ZNSL_2008_358_a14,
     author = {A. Tiskin},
     title = {Faster subsequence recognition in compressed strings},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {282--300},
     publisher = {mathdoc},
     volume = {358},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a14/}
}
TY  - JOUR
AU  - A. Tiskin
TI  - Faster subsequence recognition in compressed strings
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 282
EP  - 300
VL  - 358
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a14/
LA  - en
ID  - ZNSL_2008_358_a14
ER  - 
%0 Journal Article
%A A. Tiskin
%T Faster subsequence recognition in compressed strings
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 282-300
%V 358
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a14/
%G en
%F ZNSL_2008_358_a14
A. Tiskin. Faster subsequence recognition in compressed strings. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 282-300. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a14/