3 papers
cs.DS2026
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…
cs.DS2025
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 is defined to be the largest difference between and , where is a string of length a…
cs.DS2025
LZBE: an LZ-style compressor supporting -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…