6 papers
Computing Smallest Suffixient Arrays in Sublinear Time
Hiroto Fujimaru, Gonzalo Navarro, Francisco Olivares +3
A suffixient array is a novel data structure that, when combined with an index providing direct access on a text , allows us to answer a variety of pattern matching queries. In…
Smallest Suffixient Sets: Effectiveness, Resilience, and Calculation
Hiroto Fujimaru, Gonzalo Navarro, Giuseppe Romana +1
A suffixient set is a novel combinatorial object that captures the essential information of repetitive strings in a way that, provided with a random access mechanism, supports vari…
On the sensitivity of CDAWG-grammars
Hiroto Fujimaru, Shunsuke Inenaga
The compact directed acyclic word graph (CDAWG) [Blumer et al. 1987] of a string is the minimal compact automaton that recognizes all the suffixes of the string. CDAWGs can be used…
On the number of MUSs crossing a position
Hiroto Fujimaru, Takuya Mieno, Shunsuke Inenaga
A string is said to be a minimal unique substring (MUS) of a string if occurs exactly once in , and any proper substring of occurs at least twice in . It is k…
Constant sensitivity on the CDAWGs
Rikuya Hamai, Hiroto Fujimaru, 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…
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…