講演名 | 2019-10-25 スライド窓上の極小非反復部分文字列 三重野 琢也(九大), 中島 祐人(九大), 稲永 俊介(九大), 坂内 英夫(九大), 竹田 正幸(九大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 文字列 $T$ の部分文字列 $u$ に対して,$u$ か? $T$ 中にちょうと? 1 回た?け出現し,かつ $u$ の任意の真の部分文字列か? $T$ 中に 2 回以上出現するとき,$u$ を $T$ の極小非反復部分文字列 (minimal unique substring; MUS) と呼ふ?.本稿て?は,固定幅 $d$ の窓か?長さ $n$ の入力文字列 $T$ の上をスライト?するとき,各窓に対応する $T$ の部分文字列の MUS を計算する問題を扱う.我々はます?,窓のスライト?操作に対する MUS の集合の変化を解析する.そして,スライト?窓上の MUS を $O(nlogsigma)$ 時間て?計算する $O(d)$ 領域のアルコ?リス?ムを提案する.ここて?,$sigma$ は各スライト?窓中に出現する異なる文字の種類数の最大値て?ある. |
抄録(英) | A substring $u$ of a string $T$ is called a minimal unique substring (MUS) of $T$ if $u$ occurs exactly once in $T$ and any proper substring of $u$ occurs at least twice in $T$. In this paper, we study the problem of computing MUSs in a sliding window over a given string $T$. We show how the set of MUSs can change in a sliding window over $T$, and present an $O(nlo gsigma)$-time and $O(d)$-space algorithm to compute MUSs in a sliding window of width $d$ over $T$, where $sigma$ is the maximum number of distinct characters in every window. |
キーワード(和) | 極小非反復部分文字列 / スライト?窓 |
キーワード(英) | minimal unique substrings / sliding window |
資料番号 | COMP2019-26 |
発行日 | 2019-10-18 (COMP) |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2019/10/25(から1日開催) |
開催地(和) | 北海道大学 札幌キャンパス |
開催地(英) | Sapporo Campus, Hokkaido University |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | 藤戸 敏弘(豊橋技科大) |
委員長氏名(英) | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
副委員長氏名(和) | 中野 眞一(群馬大) |
副委員長氏名(英) | Shinichi Nakano(Gunma Univ.) |
幹事氏名(和) | 大舘 陽太(熊本大) / 玉置 卓(兵庫県立大) |
幹事氏名(英) | Yota Otachi(Kumamoto Univ) / Suguru Tamaki(Univ. of Hyogo) |
幹事補佐氏名(和) | 脊戸 和寿(成蹊大) |
幹事補佐氏名(英) | Kazuhisa Seto(Seikei Univ.) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
---|---|
本文の言語 | JPN |
タイトル(和) | スライド窓上の極小非反復部分文字列 |
サブタイトル(和) | |
タイトル(英) | Minimal Unique Substrings in a Sliding Window |
サブタイトル(和) | |
キーワード(1)(和/英) | 極小非反復部分文字列 / minimal unique substrings |
キーワード(2)(和/英) | スライト?窓 / sliding window |
第 1 著者 氏名(和/英) | 三重野 琢也 / Takuya Mieno |
第 1 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 2 著者 氏名(和/英) | 中島 祐人 / Yuto Nakashima |
第 2 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 3 著者 氏名(和/英) | 稲永 俊介 / Shunsuke Inenaga |
第 3 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 4 著者 氏名(和/英) | 坂内 英夫 / Hideo Bannai |
第 4 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 5 著者 氏名(和/英) | 竹田 正幸 / Masayuki Takeda |
第 5 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
発表年月日 | 2019-10-25 |
資料番号 | COMP2019-26 |
巻番号(vol) | vol.119 |
号番号(no) | COMP-249 |
ページ範囲 | pp.57-62(COMP), |
ページ数 | 6 |
発行日 | 2019-10-18 (COMP) |