3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
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…