並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
2つの文字列X=x_1x_2…,x_mおよびY=y_1y_2…y_nに対し,それぞれの部分列(元の文字列から0文字以上を除いて得られる文字列)となる文字列Z=z_1z_2…z_kをXとYの共通部分列といい,kをその長さという.kを最大とする部分列をXとYの最長共通部分列(LCS),与えられた2つの文字列のLCSを求める問題を最長共通部分列問題(LCS問題)と呼ぶ.LCS問題は動的計画法が適用できる問題の例として広く知られており,素朴なアルゴリズムでもO(mn)時間で解くことができる.本研究では,LCS問題の変形として,並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列を求める問題を提案する.さらに,この問題を解くための漸化式を与え,LCS問題と同様に動的計画法を用いてO(mn)時間で解くことができることを示す.
- 社団法人電子情報通信学会の論文
- 2007-11-23
著者
関連論文
- RaoのRectilinear Steiner Arborescenceアルゴリズムにおける摂動の効果
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの多項式時間数え上げ (第21回 回路とシステム軽井沢ワークショップ論文集) -- (組合せ的アルゴリズム)
- 並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
- 並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
- 矩形迷路のパス決定アルゴリズム(グラフ, ペトリ, ニューラルネット及び一般)