Order-Preserving Squares in Strings
share
An order-preserving square in a string is a fragment of the form uv where u≠ v and u is order-isomorphic to v. We show that a string w of length n over an alphabet of size σ contains 𝒪(σ n) order-preserving squares that are distinct as words. This improves the upper bound of 𝒪(σ^2n) by Kociumaka, Radoszewski, Rytter, and Waleń [TCS 2016]. Further, for every σ and n we exhibit a string with Ω(σ n) order-preserving squares that are distinct as words, thus establishing that our upper bound is asymptotically tight. Finally, we design an 𝒪(σ n) time algorithm that outputs all order-preserving squares that occur in a given string and are distinct as words. By our lower bound, this is optimal in the worst case.
READ FULL TEXT