非線形テキストにおける最長共通部分文字列·部分列アルゴリズム

摘要

非線形テキストは，文字列を頂点ラベルとする有向グラフである．本論文では，二つの非線形テキストに対して，その類似性を調べる為に，二つの非線形テキストにおける最長共通部分文字列問題と最長共通部分列問題を定義し，サイクルを含まない非線形テキストに対し，O（|E_1||E_2|）時間での解法を提案する．ここで，|E'_1|，|E'_2|は二つの非線形テキストG_1，G_2のそれぞれの辺の数を表す．また，サイクルを含む非線形テキストにおけノる最長共通部分列問題のO（|E_1|+|E_2|+|E'_1||E'_2|+|V'_1||V'_2|log|∑|+|∑|log|∑|）時間での解法を提案する．ここで，|∑|はアルファベットサイズE'_1，E'_2，V'_1，V'_2はそれぞれC_1，C_2をサイクルを一つの頂点と見なし，変形した後の辺の数と頂点数を表す．