同一qグラムの出現位置間の距離を考慮した厳密文字列照合アルゴリズム
コンピュテーション研究会 (COMP研),
信学技報 Vol.119, pp.31-38
(2019)
開催日:
2019年12月13-13日
Abstract / 概要
厳密文字列照合問題は，長さ$n$のテキスト$T$と長さ$m$のパターン$P$が与えられたときに，$T$中の$P$と等しい部分文字列の出現位置をすべて見つける問題である．本研究では，$P$に含まれる同一$q$グラムの直近の出現位置間の距離を考慮した，この問題を$O((n+m)q)$時間で解くアルゴリズムを提案する．また，英文やゲノム配列等のデータセットを用いて既存のアルゴリズムと実行速度を比較し，我々のアルゴリズムが実用的に高速であることを示す．