String Periods in the Order-Preserving Model

01/04/2018
by   Garance Gourdel, et al.
0

The order-preserving model (op-model, in short) was introduced quite recently but has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time O(n), O(n n), O(n ^2 n/ n), O(n n) depending on the type of periodicity. In the most general variant the number of different periods can be as big as Ω(n^2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of such periods.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset