106 citations · 138 across the 47 of their papers we have counts for
9 papers · 1 filter
The Parameterized Suffix Tray
Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga +2
Let and be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings and over of equal length are said to pa…
Lyndon Words, the Three Squares Lemma, and Primitive Squares
Hideo Bannai, Takuya Mieno, Yuto Nakashima
We revisit the so-called "Three Squares Lemma" by Crochemore and Rytter [Algorithmica 1995] and, using arguments based on Lyndon words, derive a more general variant which consider…
Palindromic Trees for a Sliding Window and Its Applications
Takuya Mieno, Kiichi Watanabe, Yuto Nakashima +3
The palindromic tree (a.k.a. eertree) for a string of length is a tree-like data structure that represents the set of all distinct palindromic substrings of , using $O(n…
On repetitiveness measures of Thue-Morse words
Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima +3
We show that the size of the smallest string attractor of the th Thue-Morse word is 4 for any , disproving the conjecture by Mantaci et al. [ICTCS 2019]…
Towards Efficient Interactive Computation of Dynamic Time Warping Distance
Akihiro Nishi, Yuto Nakashima, Shunsuke Inenaga +2
The dynamic time warping (DTW) is a widely-used method that allows us to efficiently compare two time series that can vary in speed. Given two strings and of respective len…
Grammar-compressed Self-index with Lyndon Words
Kazuya Tsuruta, Dominik Köppl, Yuto Nakashima +3
We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data struc…
Detecting -(Sub-)Cadences and Equidistant Subsequence Occurrences
Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga +3
The equidistant subsequence pattern matching problem is considered. Given a pattern string and a text string , we say that is an \emph{equidistant subsequence} of if…
Parameterized DAWGs: efficient constructions and bidirectional pattern searches
Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian +6
Two strings and over of equal length are said to \emph{parameterized match} (\emph{p-match}) if there is a renaming bijection that…
Faster STR-EC-LCS Computation
Kohei Yamada, Yuto Nakashima, Shunsuke Inenaga +2
The longest common subsequence (LCS) problem is a central problem in stringology that finds the longest common subsequence of given two strings and . More recently, a set of…