4 papers · 1 filter
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…
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…
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…
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…