106 citations · 249 across the 101 of their papers we have counts for
105 papers · 1 filter
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)…
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…
Efficient LCE Queries and Lexicographic Minimizers on Sliding Suffix Trees
Toshiharu Minematsu, Shunsuke Inenaga
We study longest-common-extension (LCE) queries and lexicographic minimizer maintenance on the suffix tree of a sliding window. The main difficulty is that a sliding suffix tree is…