On the Number of Non-equivalent Parameterized Squares in a String
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916350842109952 |
|---|---|
| author | Hamai, Rikuya Taketsugu, Kazushi Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo |
| author_facet | Hamai, Rikuya Taketsugu, Kazushi Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04920 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Number of Non-equivalent Parameterized Squares in a String Hamai, Rikuya Taketsugu, Kazushi Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Data Structures and Algorithms Discrete Mathematics 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. |
| title | On the Number of Non-equivalent Parameterized Squares in a String |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2408.04920 |