講演抄録/キーワード |
講演名 |
2019-10-25 15:45
スライド窓上の極小非反復部分文字列 ○三重野琢也・中島祐人・稲永俊介・坂内英夫・竹田正幸(九大) COMP2019-26 |
抄録 |
(和) |
文字列 $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 / / / / / / |
文献情報 |
信学技報, vol. 119, no. 249, COMP2019-26, pp. 57-62, 2019年10月. |
資料番号 |
COMP2019-26 |
発行日 |
2019-10-18 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2019-26 |