4 papers
The Tight Upper Bound on the Number of Distinct Squares in Circular Words
Rikuya Hamai
A square is a word , where is nonempty. We show that a circular word of length contains at most distinct squares of length at most . The proof…
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…
Constant sensitivity on the CDAWGs
Rikuya Hamai, Hiroto Fujimaru, Shunsuke Inenaga
Compact directed acyclic word graphs (CDAWGs) [Blumer et al. 1987] are a fundamental data structure on strings with applications in text pattern searching, data compression, and pa…
Tight bounds on the number of non-equivalent parameterized squares in a word
Rikuya Hamai, Kazushi Taketsugu, Yuto Nakashima +3
Two words of the same length are said to be \emph{parameterized equivalent} if there exists a character bijection that transforms into . A word is called a paramet…