Skip to Main content Skip to Navigation
Journal articles

Order-Preserving Indexing

Abstract : Kubica et al. (Information Processing Letters, 2013) and Kim et al. (Theoretical Computer Science, 2014) introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same 'shape' as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O(n log log n) expected time or O(n log n) deterministic time. The index is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O(n √ log n)-time algorithm $ A preliminary version of this paper appeared in the constructing complete order-preserving suffix trees.
Document type :
Journal articles
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Friday, June 1, 2018 - 6:59:00 PM
Last modification on : Saturday, January 15, 2022 - 3:58:23 AM
Long-term archiving on: : Sunday, September 2, 2018 - 3:22:47 PM


Files produced by the author(s)


  • HAL Id : hal-01806293, version 1


Maxime Crochemore, S Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, et al.. Order-Preserving Indexing. Theoretical Computer Science, Elsevier, 2016. ⟨hal-01806293⟩



Record views


Files downloads