Compact Directed Acyclic Word Graphを定義する - Qiitaこれは「文字列アルゴリズム Advent Calendar 2017」４日目の記事です． ３日目の記事は@itomomotiによる「周期性補題」でした． ５日目の記事は@kazu0x17による「木の同型性判定」です． 昨年の文字列アルゴリズム Advent Calendar では「Suffix Tree + Suffix Array = Suffix Tray」という記事を書きました． はじめに 文字列アルゴリズム，特に文字列に対する索引が好きです． 古典的な全文索引であるCompact Directed Acyclic Word Graph (以下CDAWG)を紹介するのがこの記事です．この記事の内容は基本的に以下の論文内で示されています． Anselm Blumer, Janet Blumer, David Haussler, Andrzej Ehrenfeucht, M. T. Ch
