On the Number of Non-equivalent Parameterized Squares in a String

2024/08/09 by Hamai, Rikuya, Taketsugu, Kazushi, Nakashima, Yuto +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2408.04920

Abstract

A string s is called a parameterized square when s = xy for strings x, y and x and y are parameterized equivalent. Kociumaka et al. showed the number of parameterized squares, which are non-equivalent in parameterized equivalence, in a string of length n that contains σ distinct characters is at most 2 σ! n [TCS 2016]. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than σn, which significantly improves the best-known upper bound by Kociumaka et al.

Cited by

• Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares

Related

• Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares
• How many double squares can a string contain?
• Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a\n Word
• Order-Preserving Squares in Strings
• Optimal Square Detection Over General Alphabets