<テクニカルレポート>
An improved pattern matching algorithm for strings in terms of straight-line programs

作成者
本文言語
出版者
発行日
収録物名
出版タイプ
アクセス権
概要 We show an efficient pattern matching algorithm for strings that are succinctly described in terms of straight-line programs, in which the constants are symbols and the only operation is the concaten...ation. In this paper, both text $ T $ and pattern $ P $ are given by straight-line programs $ \tau $ and $ \rho $. The length of the text $ T $ (pattern $ P $, resp.) may grows exponentially with respect to its description size $ mid \tau mid = n (mid \rho mid = m, resp.) $. We show a new combinatorial property concerning with the periodic occurrences in a text. Based on this property, we develop an $ O(n^2m^2) $ time algorithm using $ O(nm) $ space, which outputs a compact representation of all occurrences of $ P $ in $ T $. This is superior to the algorithm proposed by Karpinski et al.[11], which runs in $ O((n + m)^4log (n + m)) $ time using $ O((n+m)^3) $ space, and finds only one occurrence. Moreover, our algorithm is much simpler than theirs.続きを見る

本文情報を非表示

trcs130.ps gz 106 KB 84  
trcs130 pdf 222 KB 31  

詳細

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

この資料を見た人はこんな資料も見ています