Name
Abstract | ||
|---|---|---|
In the order-preserving model, two strings match if they share the same relative order between the characters at the corresponding positions. This model is quite recent, but it 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(nloglogn), O(nlog2logn/logloglogn), O(nlogn) depending on the type of periodicity. In the most general variant, the number of different op-periods can be as big as Ω(n2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of op-periods. In particular, we characterize the Fine–Wilf property for coprime op-periods. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ic.2019.104463 | Information and Computation |
Keywords | DocType | Volume |
Order-preserving pattern matching,Period,Efficient algorithm | Journal | 270 |
ISSN | Citations | PageRank |
0890-5401 | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Garance Gourdel | 1 | 0 | 0.34 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Jakub Radoszewski | 3 | 624 | 50.36 |
| wojciech rytter | 4 | 130 | 17.13 |
| Arseny M. Shur | 5 | 152 | 26.47 |
| Tomasz Waleń | 6 | 706 | 39.62 |