106 citations · 138 across the 47 of their papers we have counts for
6 papers · 1 filter
Counting Lyndon Subsequences
Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga +1
Counting substrings/subsequences that preserve some property (e.g., palindromes, squares) is an important mathematical interest in stringology. Recently, Glen et al. studied the nu…
Position Heaps for Cartesian-tree Matching on Strings and Tries
Akio Nishimoto, Noriki Fujisato, Yuto Nakashima +1
The Cartesian-tree pattern matching is a recently introduced scheme of pattern matching that detects fragments in a sequential data stream which have a similar structure as a query…
On the approximation ratio of LZ-End to LZ77
Takumi Ideue, Takuya Mieno, Mitsuru Funakoshi +3
A family of Lempel-Ziv factorizations is a well-studied string structure. The LZ-End factorization is a member of the family that achieved faster extraction of any substrings (Kref…
Grammar Index By Induced Suffix Sorting
Tooru Akagi, Dominik Köppl, Yuto Nakashima +3
Pattern matching is the most central task for text indices. Most recent indices leverage compression techniques to make pattern matching feasible for massive but highly-compressibl…
Combinatorics of minimal absent words for a sliding window
Tooru Akagi, Yuki Kuhara, Takuya Mieno +4
A string is called a minimal absent word (MAW) for another string if does not occur in but the proper substrings of occur in . For example, let $Σ= \{\mathtt…
Compressed Communication Complexity of Hamming Distance
Shiori Mitsuya, Yuto Nakashima, Shunsuke Inenaga +2
We consider the communication complexity of the Hamming distance of two strings. Bille et al. [SPIRE 2018] considered the communication complexity of the longest common prefix (LCP…