106 citations · 249 across the 101 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…
Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts
Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura +2
We consider construction of the suffix tree and the directed acyclic word graph (DAWG) indexing data structures for a collection of texts, where a new symbol may be a…
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…
Diverse Palindromic Factorization is NP-Complete
Hideo Bannai, Travis Gagie, Shunsuke Inenaga +5
We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.
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…