Paper Info
Title
Faster subsequence and don't-care pattern matching on compressed texts
Abstract
Subsequence pattern matching problems on compressed text were first considered by Cégielski et al. (Window Subsequence Problems for Compressed Texts, Proc. CSR 2006, LNCS 3967, pp. 127-136), where the principal problem is: given a string T represented as a straight line program (SLP) T of size n, a string P of size m, compute the number of minimal subsequence occurrences of P in T. We present an O(nm) time algorithm for solving all variations of the problem introduced by Cégielski et al. This improves the previous best known algorithm of Tiskin (Towards approximate matching in compressed strings: Local subsequence recognition, Proc. CSR 2011), which runs in O(nm log m) time. We further show that our algorithms can be modified to solve a wider range of problems in the same O(nm) time complexity, and present the first matching algorithms for patterns containing VLDC (variable length don't care) symbols, as well as for patterns containing FLDC (fixed length don't care) symbols, on SLP compressed texts.
Year
DOI
Venue
2011
10.1007/978-3-642-21458-5_27
Lecture Notes in Computer Science
Keywords
Field
DocType
matching algorithm,local subsequence recognition,minimal subsequence occurrence,t-care pattern,nm log m,fixed length,time algorithm,towards approximate matching,principal problem,faster subsequence,time complexity,subsequence pattern
Discrete mathematics,Combinatorics,Longest increasing subsequence,Longest alternating subsequence,Approximate matching,Time complexity,Subsequence,Pattern matching,Straight-line program,Mathematics
Conference
Volume
ISSN
Citations 
6661
0302-9743
14
PageRank 
References 
Authors
0.63
15
4
Name
Order
Citations
PageRank
Takanori Yamamoto1171.08
Hideo Bannai262079.87
Shunsuke Inenaga359579.02
Masayuki Takeda490279.24