论文标题
Moni可以找到K-Mems
MONI can find k-MEMs
论文作者
论文摘要
假设我们被要求索引文本$ t [0..n -1] $，这样，在给定图案$ p [0..m -1] $的情况下，我们可以快速报告$ t $至少$ k $ times的最大$ p $。我们首先展示如何将$ O（r \ log n）$位添加到Rossi等人最近的Moni Index，其中$ r $是$ t $的burrows-wheeler转换中的运行次数，因此它支持$ O（k m \ log n）$时间中的此类查询。然后，我们展示如何在施工时给予$ K $，我们可以将查询时间缩短为$ O（m \ log n）$。
Suppose we are asked to index a text $T [0..n - 1]$ such that, given a pattern $P [0..m - 1]$, we can quickly report the maximal substrings of $P$ that each occur in $T$ at least $k$ times. We first show how we can add $O (r \log n)$ bits to Rossi et al.'s recent MONI index, where $r$ is the number of runs in the Burrows-Wheeler Transform of $T$, such that it supports such queries in $O (k m \log n)$ time. We then show how, if we are given $k$ at construction time, we can reduce the query time to $O (m \log n)$.
