Back to Search
Start Over
Order-preserving indexing.
- Source :
-
Theoretical Computer Science . Jul2016, Vol. 638, p122-135. 14p. - Publication Year :
- 2016
-
Abstract
- 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 ( n log log n ) expected time or in O ( n log 2 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 ( n log n ) -time algorithm constructing complete order-preserving suffix trees. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 638
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 115941916
- Full Text :
- https://doi.org/10.1016/j.tcs.2015.06.050