Variable Length Don't-Care Pattern Matching Problems on Compressed Texts

スポンサーリンク

概要

• 論文の詳細を見る

• Subsequence pattern matching problems on compressed text were first considered by Cegielski 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 Cegielski et al.. This improves the previous best known algorithm of Tiskin (Faster subsequence recognition in compressed strings, J. Mathematical Sciences 158(5), 759-769, 2009) which runs in O(nm1.5) 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.

• 2011-02-28

著者

• Shunsuke Inenaga

  Graduate School of Information Science and Electrical Engineering, Kyushu University

• Hideo Bannai

  Department Of Informatics Kyushu University

• Masayuki Takeda

  Department Of Informatics Kyushu University

• Takanori Yamamoto

  Department of Informatics, Kyushu University

• Shunsuke Inenaga

  Graduate School Of Information Science And Electrical Engineering Kyushu University

• Takanori Yamamoto

  Department Of Informatics Kyushu University

関連論文

• Towards Modeling Stored-value Electronic Money Systems
• Modeling Costs of Access Control with Various Key Management Systems
• Variable Length Don't-Care Pattern Matching Problems on Compressed Texts
• Online Prediction over Permutahedron
• 圧縮テキスト上でのq-gram非重複頻度の効率的な計算とその応用
• 高速かつ省領域な線形時間LZ分解アルゴリズム

スポンサーリンク