Standard

Faster subsequence recognition in compressed strings. / Tiskin, A.

In: Journal of Mathematical Sciences , Vol. 158, No. 5, 01.05.2009, p. 759-769.

Research output: Contribution to journal › Article › peer-review

Harvard

Tiskin, A 2009, 'Faster subsequence recognition in compressed strings', Journal of Mathematical Sciences , vol. 158, no. 5, pp. 759-769. https://doi.org/10.1007/s10958-009-9396-0

APA

Tiskin, A. (2009). Faster subsequence recognition in compressed strings. Journal of Mathematical Sciences , 158(5), 759-769. https://doi.org/10.1007/s10958-009-9396-0

Vancouver

Tiskin A. Faster subsequence recognition in compressed strings. Journal of Mathematical Sciences . 2009 May 1;158(5):759-769. https://doi.org/10.1007/s10958-009-9396-0

Author

Tiskin, A. / Faster subsequence recognition in compressed strings. In: Journal of Mathematical Sciences . 2009 ; Vol. 158, No. 5. pp. 759-769.

BibTeX

@article{d184db968c794ff7aabac8b9577945d0,
title = "Faster subsequence recognition in compressed strings",
abstract = "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, and an uncompressed pattern of length n, C{\'e}gielski et al. gave an algorithm for local subsequence recognition running in time O(mn2) . We improve the running time to O(mn1.5) . Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time O(m n1.5); the same problem with a compressed pattern is known to be NP-hard. Bibliography: 22 titles. {\textcopyright} 2009 Springer Science+Business Media, Inc.",
author = "A. Tiskin",
year = "2009",
month = may,
day = "1",
doi = "10.1007/s10958-009-9396-0",
language = "English",
volume = "158",
pages = "759--769",
journal = "Journal of Mathematical Sciences",
issn = "1072-3374",
publisher = "Springer Nature",
number = "5",

}

RIS

TY - JOUR

T1 - Faster subsequence recognition in compressed strings

AU - Tiskin, A.

PY - 2009/5/1

Y1 - 2009/5/1

N2 - 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, and an uncompressed pattern of length n, Cégielski et al. gave an algorithm for local subsequence recognition running in time O(mn2) . We improve the running time to O(mn1.5) . Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time O(m n1.5); the same problem with a compressed pattern is known to be NP-hard. Bibliography: 22 titles. © 2009 Springer Science+Business Media, Inc.

AB - 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, and an uncompressed pattern of length n, Cégielski et al. gave an algorithm for local subsequence recognition running in time O(mn2) . We improve the running time to O(mn1.5) . Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time O(m n1.5); the same problem with a compressed pattern is known to be NP-hard. Bibliography: 22 titles. © 2009 Springer Science+Business Media, Inc.

UR - http://www.scopus.com/inward/record.url?scp=67349251202&partnerID=8YFLogxK

U2 - 10.1007/s10958-009-9396-0

DO - 10.1007/s10958-009-9396-0

M3 - Article

AN - SCOPUS:67349251202

VL - 158

SP - 759

EP - 769

JO - Journal of Mathematical Sciences

JF - Journal of Mathematical Sciences

SN - 1072-3374

IS - 5

ER -

ID: 127710042