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

詳細

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