ファクターオラクルを用いた反復文字列の抽出アルゴリズムの改良

摘要

与えらた文字列pに対して，pの中に少なくとも2回以上出現するpの部分文字列を反復文字列と言う．本研究では，反復文字列の中でも，文字列pの各接頭辞に対して，最長の反復接尾辞の長さを求めることを目的としている. この問題に対し，ファクターオラクルというデータ構造を川いたアルゴリズムがLebbvreらにより提案されている[5]. このアルゴリズムは，pのすべての接頭辞に対して，最長ではないがある反復接尾辞を，pの長さの線形時間(O(｜p｜))で求めることができる. 本研究では，Lefebvreらのアルゴリズムを改良し，O(｜p｜)でより長い反復接尾辞を抽出するアルゴリズムを提案する．