From the 1 of 10 linked papers with an AI index.
10 papers
Sensitivity and Size Relationships of the Lempel-Ziv Factorization
Hiroki Shibata, Yuto Fujie
The Lempel-Ziv (LZ) factorization is one of the most fundamental methods for compressing highly repetitive strings, and the number of phrases in its factorization is considered a r…
Relaxation of Square-Freeness
Hiroki Shibata, Takuya Mieno, Dominik Köppl +1
The paper studies nonrepetitive sequences under relaxed equivalence relations, introducing ℓ⁺-squares and constructing infinite words that avoid such squares for parameterized and…
Compact Enumeration of Maximal Closed Substrings in Run-Length Encoded Strings
Haruki Umezaki, Hiroki Shibata, Yuto Nakashima +1
A string is closed if , or if 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)…
Counting Distinct (Non-)Crossing Substrings in Optimal Time
Haruki Umezaki, Hiroki Shibata, Dominik Köppl +3
Let be a string of length . The problem of counting factors crossing a position -- Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Lecroq, and…
String Representation Based on Substring Equation Systems
Hiroki Shibata, Hideo Bannai
Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. Many compressi…