King's College London

Research portal

Order-Preserving Indexing

Research output: Contribution to journalArticlepeer-review

Maxime Crochemore, Costas S Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen

Original languageEnglish
Pages (from-to)122-135
Number of pages14
JournalTheoretical Computer Science
Early online date11 Jul 2015
Accepted/In press23 Jun 2015
E-pub ahead of print11 Jul 2015
Published25 Jul 2016


King's Authors


Kubica et al. [33] and Kim et al. [29] 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(nlog⁡log⁡n)O(nlog⁡log⁡n) expected time or in O(nlog2⁡log⁡n/log⁡log⁡log⁡n)O(nlog2⁡log⁡n/log⁡log⁡log⁡n) worst-case time. It 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 View the MathML sourceO(nlog⁡n)-time algorithm constructing complete order-preserving suffix trees.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454