کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433742 | 689618 | 2016 | 14 صفحه PDF | دانلود رایگان |
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(nloglogn)O(nloglogn) expected time or in O(nlog2logn/logloglogn)O(nlog2logn/logloglogn) 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(nlogn)-time algorithm constructing complete order-preserving suffix trees.
Journal: Theoretical Computer Science - Volume 638, 25 July 2016, Pages 122–135