Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00453-008-9263-2
Title: Compressed indexes for approximate string matching
Authors: Chan, H.-L.
Lam, T.-W.
Sung, W.-K. 
Tam, S.-L.
Wong, S.-S. 
Keywords: Approximate string matching
Compressed index
Issue Date: 2010
Source: Chan, H.-L., Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, S.-S. (2010). Compressed indexes for approximate string matching. Algorithmica (New York) 58 (2) : 263-281. ScholarBank@NUS Repository. https://doi.org/10.1007/s00453-008-9263-2
Abstract: We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log∈nlog∈log∈n) time. The previously best solution achieving this time complexity requires an index of O(nlog∈n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog∈nlog∈log∈n+occ) time, and k-error matching, for any k>2, in O(m k-1log∈nlog∈log∈n+occ) time. © 2008 Springer Science+Business Media, LLC.
Source Title: Algorithmica (New York)
URI: http://scholarbank.nus.edu.sg/handle/10635/38987
ISSN: 01784617
DOI: 10.1007/s00453-008-9263-2
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

9
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

6
checked on Dec 5, 2017

Page view(s)

61
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.