License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2023.13
URN: urn:nbn:de:0030-drops-179676
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17967/
Gawrychowski, Paweł ;
Ghazawi, Samah ;
Landau, Gad M.
Order-Preserving Squares in Strings
Abstract
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 ?(σ²n) 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.
BibTeX - Entry
@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2023.13,
author = {Gawrychowski, Pawe{\l} and Ghazawi, Samah and Landau, Gad M.},
title = {{Order-Preserving Squares in Strings}},
booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
pages = {13:1--13:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-276-1},
ISSN = {1868-8969},
year = {2023},
volume = {259},
editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17967},
URN = {urn:nbn:de:0030-drops-179676},
doi = {10.4230/LIPIcs.CPM.2023.13},
annote = {Keywords: repetitions, distinct squares, order-isomorphism}
}
Keywords: |
|
repetitions, distinct squares, order-isomorphism |
Collection: |
|
34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
21.06.2023 |