106 citations · 239 across the 67 of their papers we have counts for
12 papers · 1 filter
Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl +1
The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it.…
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…
The smallest grammar problem revisited
Hideo Bannai, Momoko Hirayama, Danny Hucke +4
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors,…
On Longest Common Property Preserved Substring Queries
Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga +3
We revisit the problem of longest common property preserving substring queries introduced by~Ayad et al. (SPIRE 2018, arXiv 2018). We consider a generalized and unified on-line set…
Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets
Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2
We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either requir…
Order-Preserving Pattern Matching Indeterminate Strings
Diogo Costa, Luís M. S. Russo, Rui Henriques +2
Given an indeterminate string pattern and an indeterminate string text , the problem of order-preserving pattern matching with character uncertainties (OPPM) is to find a…