106 citations · 150 across the 16 of their papers we have counts for
5 papers · 1 filter
Efficiently Finding All Maximal -gapped Repeats
Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga +2
For , an -gapped repeat in a word is a factor of such that ; the two factors in such a repeat are called arms, while the factor is…
Deterministic Sparse Suffix Sorting in the Restore Model
Johannes Fischer, Tomohiro I, Dominik Köppl
Given a text of length , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of in $O(c \sqrt{\lg n}…
Dynamic index, LZ factorization, and LCE queries in compressed space
Takaaki Nishimoto, I Tomohiro, Shunsuke Inenaga +2
In this paper, we present the following results: (1) We propose a new \emph{dynamic compressed index} of space, that supports searching for a pattern in the current text…
Beyond the Runs Theorem
Johannes Fischer, Štěpán Holub, Tomohiro I +1
Recently, a short and elegant proof was presented showing that a binary word of length contains at most runs. Here we show, using the same technique and a computer search…
Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets
Yuto Nakashima, Tomohiro I, Shunsuke Inenaga +2
We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marke…