<テクニカルレポート>
Pattern Matching in Text Compressed by Using Antidictionaries

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 In this paper we focus on the problem of compressed pattern matching for the text compression using antidictionaries, which is a new compression scheme proposed recently by Crochemore et al. (1998). W...e show an algorithm which preprocesses a pattern of length $ m $ and an antidictionary M in $ O(m^2 + left |M\right |) $ time, and then scans a compressed text of length n in $ O(n +r) $ time to find all pattern occurrences, where $ left |M\right | $ is the total length of strings in $ M $ and $ r $ is the number of the pattern occurrences.続きを見る

本文情報を非表示

trcs157 pdf 272 KB 47  
trcs157.ps gz 126 KB 24  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20