<テクニカルレポート>
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 concatena...tion. In this paper, both text T and pattern P are given by straight-line programs T and P. The length of the text T (pattern P, resp.) may grows exponentially with respect to its description size $ mid T mid = n left(mid P mid = m, resp.\right). $ We show a new combinatorial property concerning with the periodic occurrences in a text. Based on this property, we develop an $ Oleft(n^2m^2\right) $ 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 $ Oleft((n+m)^4log (n+m)\right) $ time using $ O left(( n+m)^3\right) $ space, and finds only one occurrence. Moreover, our algorithm is much simpler than theirs.続きを見る

本文情報を非表示

doi-tr-130 pdf 740 KB 112  

詳細

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