5 papers · 1 filter
Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura +2
A string is said to be a minimal absent word (MAW) for a string if does not occur in and any proper substring of occurs in . We focus on non-trivial MAWs whi…
Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga +2
The directed acyclic word graph (DAWG) of a string of length is the smallest (partial) DFA which recognizes all suffixes of with only nodes and edges. In this pa…
Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
Takuya Mieno, Yuki Kuhara, Tooru Akagi +5
A substring of a string is called a minimal unique substring (MUS) of if occurs exactly once in and any proper substring of occurs at least twice in . A…
Linear-size CDAWG: new repetition-aware indexing and grammar compression
Takuya Takagi, Keisuke Goto, Yuta Fujishige +2
In this paper, we propose a novel approach to combine \emph{compact directed acyclic word graphs} (CDAWGs) and grammar-based compression. This leads us to an efficient self-index,…
Faster STR-IC-LCS computation via RLE
Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga +2
The constrained LCS problem asks one to find a longest common subsequence of two input strings and with some constraints. The STR-IC-LCS problem is a variant of the constra…