| 講演名 | 2006-06-23 ファクターオラクルを用いた反復文字列の抽出アルゴリズムの改良 岩崎 久史, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 与えらた文字列pに対して,pの中に少なくとも2回以上出現するpの部分文字列を反復文字列と言う.本研究では,反復文字列の中でも,文字列pの各接頭辞に対して,最長の反復接尾辞の長さを求めることを目的としている.この問題に対し,ファクターオラクルというデータ構造を用いたアルゴリズムがLefebvreらにより提案されている.このアルゴリズムは,pのすべての接頭辞に対して,最長ではないがある反復接尾辞を,pの長さの線形時間(O(|p|))で求めることができる.本研究では,Lefebvreらのアルゴリズムを改良し,(O(|p|))でより長い反復接尾辞を抽出するアルゴリズムを提案する.また,いくつかのデータによる実験結果も示す. |
| 抄録(英) | We provide a linear time and space algorithm a repeated suffix for each prefix of a given string p. Our algorithm is improvement of the algorithm by Lefebvre and Lecroq. This new algorithm gives repeated suffixes longer than those computed by Lefebvre-Lecroq algorithm. The algorithm runs within linear time and space in |p|. Some experiments are given to demonstrate the performance of this algorithm. |
| キーワード(和) | ファクターオラクル / 反復文字列探索 / 部分文字列探索 |
| キーワード(英) | factor oracle / repetition search / substring search |
| 資料番号 | COMP2006-22 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2006/6/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ファクターオラクルを用いた反復文字列の抽出アルゴリズムの改良 |
| サブタイトル（和） | |
| タイトル（英） | Improvement of repeat search using factor oracles |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ファクターオラクル / factor oracle |
| キーワード(2)（和/英） | 反復文字列探索 / repetition search |
| キーワード(3)（和/英） | 部分文字列探索 / substring search |
| 第 1 著者 氏名（和/英） | 岩崎 久史 / Hisashi IWASAKI |
| 第 1 著者 所属（和/英） | 東京工業大学大学院情報理工学研究科 数理・計算科学専攻 Dept. of Mathematical and Computing Sciences Tokyo Institute of Technology |
| 発表年月日 | 2006-06-23 |
| 資料番号 | COMP2006-22 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 128 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |