106 citations · 138 across the 47 of their papers we have counts for
5 papers · 1 filter
Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi +2
In this paper, we present the first study of the computational complexity of converting an automata-based text index structure, called the Compact Directed Acyclic Word Graph (CDAW…
Linear-time computation of generalized minimal absent words for multiple strings
Kouta Okabe, Takuya Mieno, Yuto Nakashima +2
A string is called a minimal absent word (MAW) for a string if does not occur as a substring in and all proper substrings of occur in . MAWs are well-studied…
Computing SEQ-IC-LCS of Labeled Graphs
Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga
We consider labeled directed graphs where each vertex is labeled with a non-empty string. Such labeled graphs are also known as non-linear texts in the literature. In this paper, w…
Tight bounds for the sensitivity of CDAWGs with left-end edits
Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga
Compact directed acyclic word graphs (CDAWGs) [Blumer et al. 1987] are a fundamental data structure on strings with applications in text pattern searching, data compression, and pa…
Optimal LZ-End Parsing is Hard
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita +3
LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occ…