106 citations · 249 across the 101 of their papers we have counts for
112 papers
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 with periods and also has period . For parameterized strings, Apo…
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)…
Relaxation of Square-Freeness
Hiroki Shibata, Takuya Mieno, Dominik Köppl +1
We extend the analysis of nonrepetitive sequences of Entringer et al. [Journal of Combinatorial Theory, 1974] to relaxations of equality testing under nonstandard equivalence relat…
Output-Sensitive Construction of CDAWGs from BWT-Runs
Yuta Tsuruzono, Hiroki Arimura, Shunsuke Inenaga
The compact directed acyclic word graph (CDAWG) of a string can be viewed in two equivalent ways: as the edge-compacted DAWG of the string, and as the DAG obtained from the suffix…
Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars
Taiki Kaneda, Hiroki Arimura, Shunsuke Inenaga
We study fully persistent dynamic strings with equality and longest common extension (LCE) queries. Straightforward full persistence is problematic for the splay-based FeST structu…