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 metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01806293
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 1, 2018 - 6:59:00 PM
Last modification on : Friday, April 12, 2019 - 10:18:10 AM
Long-term archiving on : Sunday, September 2, 2018 - 3:22:47 PM

File

op_suftree.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01806293, version 1

Citation

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

Share

Metrics

Record views

86

Files downloads

214