19 citations · 19 across the 11 of their papers we have counts for
15 papers
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…
Height-bounded Lempel-Ziv encodings
Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian +2
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access…
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…
Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura +2
A string is said to be a minimal absent word (MAW) for a string if does not occur in and any proper substring of occurs in . We focus on non-trivial MAWs whi…
Optimal LZ-End Parsing is Hard
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita +3
LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the parsing has a previous occurrence, with the additional constraint that the previous occ…
Computing palindromes on a trie in linear time
Takuya Mieno, Mitsuru Funakoshi, Shunsuke Inenaga
A trie is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually dist…