11 papers · 1 filter
Disproving the Greedy Superstring Conjecture
Hiroki Shibata
The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that re…
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…
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)…
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…
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…