Abstract:Two words $x,y$ of the same length are said to be \emph{parameterized equivalent} if there exists a character bijection that transforms $x$ into $y$. A word $w$ is called a parameterized square if $w$ is a concatenation of two parameterized equivalent words. Kociumaka et al. [TCS 2016] showed that in a word of length $n$ that contains $\sigma$ distinct characters, the number of \emph{parameterized squares} that are non-equivalent with respect to parameterized equivalence is at most $2 \sigma! n$. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than $\sigma n$, which significantly improves the best-known upper bound by Kociumaka et al. Moreover, we construct a family of words containing $\Omega(\sigma n)$ non-equivalent parameterized squares, which demonstrates that the upper bound is asymptotically tight.
From: Yuto Nakashima [view email]
[v1]
Fri, 9 Aug 2024 08:02:51 UTC (87 KB)
[v2]
Wed, 2 Sep 2026 07:19:58 UTC (91 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。