106 citations · 249 across the 101 of their papers we have counts for
12 papers · 1 filter
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…
Space-Efficient Algorithms for Computing Minimal/Shortest Unique Substrings
Takuya Mieno, Dominik Köppl, Yuto Nakashima +3
Given a string of length , a substring of is called a shortest unique substring (SUS) for an interval if (a) occurs exactly once in , (b) $u…
c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda +4
Given a dynamic set of strings of total length whose characters are drawn from an alphabet of size , a keyword dictionary is a data structure built on that provi…