106 citations · 239 across the 67 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 15 cited
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…
cs.FL2015★ 6 cited
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.
cs.DS2015
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…