3 citations · 8 across the 32 of their papers we have counts for
9 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…
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…
The Parameterized Position Heap of a Trie
Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2
Let and be disjoint alphabets of respective size and . Two strings over of equal length are said to parameterized match (p-match) if there is a bijection $…