圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム

摘要

直線的プログラム(Straight line program, SLP)は単元集合を生成する文脈自由文法の部分クラスとみなすことができ，そこで生成される文字列の長さは，変数の個数nに対して指数的に長くなりうる．そのため，SLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには，陽に展開することなく処理を行うことが必要不可欠となる．本研究では，SLPとして表現された2つの文字列の最長共通部分文字列の長さを求める問題をO(n{sup}4 log n)時間，O(n{sup}4)領域で解くアルゴリズムを示す．またSLPとして表現された文字列に含まれるすべての回文を検出する問題に対して，O(n{sup}4)時間，O(n{sup}2)領域で解くアルゴリズムを示す．