<テクニカルレポート>
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 157  
trcs130 pdf 222 KB 84  

詳細

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

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