はてなブックマーク

本記事は、「文字列アルゴリズム Advent Calender 2017」 9日目の記事です。 8日目の記事は @kampersanda 氏による「ダブル配列で決定性有限オートマトンを表現する」でした。 10日目の記事は @tsukasa_diary 氏による「BDDとZDD -ブール関数と集合族の圧縮処理-」です。 ちなみに私は去年の Advent Calender では 、Range Minimum Query という記事も書いています。お時間のある方はそちらもぜひご覧ください。 また、本記事の内容はこちらの論文[1]に書かれています。 さらに日本語のこちらの本[2]にも、書かれていたはずです(私の記憶が正しければ...)。 はじめに 本記事では、最短超文字列問題1という問題を扱います。 最短超文字列問題は、文字列の集合が与えられたときに、 それらすべてを部分文字列として含む文字列（超