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

被引：0

作者：

Hamai, Rikuya ^{[1
]}

Taketsugu, Kazushi ^{[1
]}

Nakashima, Yuto ^{[2
]}

Inenaga, Shunsuke ^{[2
]}

Bannai, Hideo ^{[3
]}

机构：

[1] Kyushu Univ, Dept Informat Sci & Technol, Fukuoka, Japan

[2] Kyushu Univ, Dept Informat, Fukuoka, Japan

[3] Tokyo Med & Dent Univ, M&D Data Sci Ctr, Tokyo, Japan

来源：

STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2024 | 2025年 / 14899卷

关键词：

Parameterized equivalence of strings; Squares; Periodicity; PERIODICITY;

D O I：

10.1007/978-3-031-72200-4_13

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 sigma distinct characters is at most 2 sigma!n [TCS 2016]. 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.

引用

页码：174 / 183

页数：10

共 20 条

[1] ALPHABET DEPENDENCE IN PARAMETERIZED MATCHING [J].

AMIR, A ;

FARACH, M ;

MUTHUKRISHNAN, S .

INFORMATION PROCESSING LETTERS, 1994, 49 (03) :111-115

[2] Periodicity and repetitions in parameterized strings [J].

Apostolico, Alberto ;

Giancarlo, Raffaele .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (09) :1389-1398

[3] Parameterized pattern matching: Algorithms and applications [J].

Baker, BS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1996, 52 (01) :28-42

[4]

Brlek S, 2022, Arxiv, DOI arXiv:2204.10204

[5]

Deguchi S, 2008, PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008, P84

[6] UNIQUENESS THEOREMS FOR PERIODIC FUNCTIONS [J].

FINE, NJ ;

WILF, HS .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 16 (01) :109-&

[7] How many squares can a string contain? [J].

Fraenkel, AS ;

Simpson, J .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1998, 82 (01) :112-120

[8]

Fujisato N, 2019, LECT NOTES COMPUT SC, V11811, P382, DOI 10.1007/978-3-030-32686-9_27

[9]

Ganguly A, 2017, PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P397

[10]

Gawrychowski P, 2023, Arxiv, DOI arXiv:2302.00724

← 1 2 →