最長共通接頭辞情報のためのコンパクトなデータ構造
スポンサーリンク
概要
- 論文の詳細を見る
文字列検索のためのデータ構造の一部である,接尾辞間の最長一致接頭辞長(lcp)を格納するコンパクトなデータ構造を提案する.文字列の接尾辞配列と共に用いることで,接尾辞間のlcpを定数時間で求めることができる.データ構造のサイズは,接尾辞配列中で隣接する接尾辞間のlcpを計算する際は長さnの文字列に対し2n+o(n)ビット,任意の接尾辞間では6n+o(n)ビットとなる.既存手法では最悪事はnlog_2nビット必要である.
- 2002-03-15