TY - JOUR

T1 - Order-preserving indexing

AU - Crochemore, Maxime

AU - Iliopoulos, Costas S.

AU - Kociumaka, Tomasz

AU - Kubica, Marcin

AU - Langiu, Alessio

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

AU - Rytter, Wojciech

AU - Waleń, Tomasz

PY - 2016/7/25

Y1 - 2016/7/25

N2 - 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) expected time or in 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 O(nlog n)-time algorithm constructing complete order-preserving suffix trees.

AB - 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) expected time or in 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 O(nlog n)-time algorithm constructing complete order-preserving suffix trees.

KW - Order-preserving indexing

KW - Order-preserving matching

KW - Suffix tree

UR - http://www.scopus.com/inward/record.url?scp=84937459238&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937459238&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.06.050

DO - 10.1016/j.tcs.2015.06.050

M3 - Article

AN - SCOPUS:84937459238

SN - 0304-3975

VL - 638

SP - 122

EP - 135

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -