Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2025
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…
cs.DS2024
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…