Jeudi 27 février 2025, 14:00 à 15:00

salle de séminaire du département d'informatique

Samah Ghazawi

(Department of Software Engineering, Braude, College of Engineering, Karmiel, Israel)

A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from purely combinatorial and algorithmic angles. One of the most basic questions is how many distinct squares, i.e., distinct strings of the form UU, a string of length n can contain as fragments. It turns out that this is always O(n), and the bound cannot be improved to sublinear in n [Fraenkel and Simpson, JCTA 1998].
Quartics were introduced by Apostolico and Brimkov [TCS 2000] as analogues of squares in two dimensions. Charalampopoulos, Radoszewski, Rytter, Waleń, and Zuba [ESA 2020] proved that the number of distinct quartics in an nXn 2D string is O(n^2 log^2 n) and that they can be computed in O(n^2 log^2 n) time.
In this talk, first, we will construct an infinite family of nXn 2D strings with Omega(n^2 log n) distinct quartics. Second, we will show that the number of distinct quartics in an nXn 2D string is O(n^2 log n) and they can be computed in the worst-case optimal O(n^2 log n) time.