106 citations · 187 across the 45 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 $…
Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga +2
For a string , a palindromic substring is said to be a \emph{shortest unique palindromic substring} () for an interval in , if occ…
Computing longest palindromic substring after single-character or block-wise edits
Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga +2
Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of…
Efficiently computing runs on a trie
Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga +2
A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that c…