Yuto Nakashima

The Parameterized Periodicity Lemma

Rikuya Hamai, Yuto Nakashima, Shunsuke Inenaga

Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least $p + q - d$ with periods $p$ and $q$ also has period $d = g cd (p, q)$ . For parameterized strings, Apo…

Compact Enumeration of Maximal Closed Substrings in Run-Length Encoded Strings

Haruki Umezaki, Hiroki Shibata, Yuto Nakashima +1

A string $w$ is closed if $∣ w ∣ = 1$ , or if $w$ has a non-empty proper border occurring only as its prefix and suffix. A maximal closed substring (MCS) is a maximal occurrence of a cl…

Online computation of maximal closed substrings

Hiroki Shibata, Haruki Umezaki, Takuya Mieno +2

A non-empty string is closed if it has length one or its longest border appears exactly twice in the string. An occurrence of a closed substring is a maximal closed substring (MCS)…

Sensitivity of Repetitiveness Measures to String Reversal

Hideo Bannai, Yuto Fujie, Peaker Guo +4

We study the impact that string reversal can have on several repetitiveness measures. First, we exhibit an infinite family of strings where the number, $r$ , of runs in the run-leng…

Online Computation of Palindromes and Suffix Trees on Tries

Hiroki Shibata, Mitsuru Funakoshi, Takuya Mieno +5

We consider the problems of computing maximal palindromes and distinct palindromes in a trie. A trie is a natural generalization of a string, which can be seen as a single-path tre…

Fast Computation of $k$ -Runs, Parameterized Squares, and Other Generalised Squares

Yuto Nakashima, Jakub Radoszewski, Tomasz Waleń

A $k$ -mismatch square is a string of the form $X Y$ where $X$ and $Y$ are two equal-length strings that have at most $k$ mismatches. Kolpakov and Kucherov [Theor. Comput. Sci., 2003…

Nyldon Factorization of Thue-Morse Words and Fibonacci Words

Kaisei Kishi, Kazuki Kai, Yuto Nakashima +2

The Nyldon factorization is a string factorization that is a non-decreasing product of Nyldon words. Nyldon words and Nyldon factorizations are recently defined combinatorial objec…

Tight Additive Sensitivity on LZ-style Compressors and String Attractors

Yuto Fujie, Hiroki Shibata, Yuto Nakashima +1

The worst-case additive sensitivity of a string repetitiveness measure $c$ is defined to be the largest difference between $c (w)$ and $c (w^{'})$ , where $w$ is a string of length $n$ a…

Counting Distinct (Non-)Crossing Substrings in Optimal Time

Haruki Umezaki, Hiroki Shibata, Dominik Köppl +3

Let $w$ be a string of length $n$ . The problem of counting factors crossing a position -- Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Lecroq, and…

LZBE: an LZ-style compressor supporting $O (lo g n)$ -time random access

Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi +1

An LZ-like factorization of a string divides it into factors, each being either a single character or a copy of a preceding substring. While grammar-based compression schemes suppo…

cs.DM2024

On the compressiveness of the Burrows-Wheeler transform

Hideo Bannai, Tomohiro I, Yuto Nakashima

The Burrows-Wheeler transform (BWT) is a reversible transform that converts a string $w$ into another string $BWT (w)$ . The size of the run-length encoded BWT (RLBWT) can b…

cs.DS2024

Tight bounds on the number of non-equivalent parameterized squares in a word

Rikuya Hamai, Kazushi Taketsugu, Yuto Nakashima +3

Two words $x, y$ of the same length are said to be \emph{parameterized equivalent} if there exists a character bijection that transforms $x$ into $y$ . A word $w$ is called a paramet…

cs.DS2024

Edit and Alphabet-Ordering Sensitivity of Lex-parse

Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi +2

We investigate the compression sensitivity [Akagi et al., 2023] of lex-parse [Navarro et al., 2021] for two operations: (1) single character edit and (2) modification of the alphab…

cs.DS2024★ 1 cited

Subsequence Matching and LCS under Cartesian-Tree Equivalence

Taketo Tsujimoto, Yuki Yonemoto, Hiroki Shibata +3

Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural mod…

Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph

Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi +2

In this paper, we present the first study of the computational complexity of converting an automata-based text index structure, called the Compact Directed Acyclic Word Graph (CDAW…

Linear-time computation of generalized minimal absent words for multiple strings

Kouta Okabe, Takuya Mieno, Yuto Nakashima +2

A string $w$ is called a minimal absent word (MAW) for a string $S$ if $w$ does not occur as a substring in $S$ and all proper substrings of $w$ occur in $S$ . MAWs are well-studied…

Computing SEQ-IC-LCS of Labeled Graphs

Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga

We consider labeled directed graphs where each vertex is labeled with a non-empty string. Such labeled graphs are also known as non-linear texts in the literature. In this paper, w…

cs.DS2023★ 2 cited

Tight bounds for the sensitivity of CDAWGs with left-end edits

Hiroto Fujimaru, Yuto Nakashima, Shunsuke Inenaga

Compact directed acyclic word graphs (CDAWGs) [Blumer et al. 1987] are a fundamental data structure on strings with applications in text pattern searching, data compression, and pa…