情報処理学会 第79回全国大会講演要旨

順列にはパターンマッチング問題が定義されており，「あるパターンを含むか否か」によって，スタックソートやフロアプランなど，多くの問題の解を記述できるという結果が数多く知られている．本研究では，有用なパターンの発見を目指し，2つの順列に共通して現れるパターンをすべて列挙する問題を考える．最長共通パターンを1つ求める問題でもNP完全であることが知られており，実用的に高速な列挙についてはあまり研究されていなかった．本研究では順列決定グラフと呼ばれるデータ構造を利用したアルゴリズムを提案し，実用上高速に動作することを実験的に確認する．