CPM 2017 アクセプト (1)

文字列情報学研究室の久保井啓太君と藤重雄大君の論文が CPM 2017 にアクセプトされました。

文字列情報学研究室の久保井啓太君 (執筆時 M2 - 2017年3月卒業) と藤重雄大君 (現在 D1) の論文

"Faster STR-IC-LCS computation via RLE"
Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

CPM 2017 にアクセプトされました。STR-IC-LCS とは、与えられた2つの文字列の最長共通部分列 (LCS - Longest Common Subsequence)を求める問題について、解となる部分列が特定の部分文字列を持たなければならないという制約を加えた問題です。本論文では、与えられた長さ M, N の文字列の連長圧縮 (Run Length Encoding)表現がそれぞれ m, n であるとき、STR-IC-LCS 問題を解く O(mN + Nm) 時間で動作するアルゴリズムを提案しました。これは従来は O(MN) 時間のアルゴリズムを改善するもので、特に文字列の連長圧縮表現のサイズが小さい場合に有効なアルゴリズムとなっています。

CPM 2017 は、7月4日~7月6日に、ポーランドのワルシャワにて開催されます。