| 作成者 |
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 権利関係 |
|
| 関連DOI |
|
| 関連DOI |
|
|
|
|
|
| 関連URI |
|
|
|
|
|
| 関連URI |
|
| 関連HDL |
|
| 関連情報 |
|
|
|
|
|
| 概要 |
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) 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 (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.続きを見る
|
Mendeley出力
camera-ready