@inproceedings{af937a0cd34841778b3358c08a479f15,
title = "On the Number of Distinct Squares in Finite Sequences: Some Old and New Results",
abstract = "A square is a word of the form uu, where u is a finite word. The problem of determining the number of distinct squares in a finite word was initially explored by Fraenkel and Simpson in 1998. They proved that the number of distinct squares, denoted as Sq (w), in a finite word w of length n is upper bounded by 2n and conjectured that Sq (w) is no larger than n. In this note, we review some old and new findings concerning the square-counting problem and prove that Sq (w) ≤ n- Θ(log 2(n) ).",
author = "Sre{\v c}ko Brlek and Shuo Li",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 14th International Conference on Combinatorics on Words, WORDS 2023 ; Conference date: 12-06-2023 Through 16-06-2023",
year = "2023",
doi = "10.1007/978-3-031-33180-0\_3",
language = "英语",
isbn = "9783031331794",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "35--44",
editor = "Anna Frid and Robert Merca{\c s}",
booktitle = "Combinatorics on Words - 14th International Conference, WORDS 2023, Proceedings",
address = "德国",
}