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

作成者 作成者姓名 所属機関 所属機関名 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 作成者姓名 所属機関 所属機関名 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 作成者姓名 所属機関 所属機関名 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 英語 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 1997-01 130 accepted open access 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 3000 査読無 DOI Technical Report || 130 http://www.i.kyushu-u.ac.jp/research/report.html テクニカルレポート 2009.04.22 2017.01.20