106 citations · 239 across the 67 of their papers we have counts for
10 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…
Longest Square Subsequence Problem Revisited
Takafumi Inoue, Shunsuke Inenaga, Hideo Bannai
The longest square subsequence (LSS) problem consists of computing a longest subsequence of a given string that is a square, i.e., a longest subsequence of form appearing…
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…