CLR cover
Previous problem

Problem 31: Order-Preserving Patterns

Next problem

Searching time series or list of values for patterns representing specific fluctuations of the values requires a redefinition of the notion of pattern. The question is to deal with the recognition of peaks, breakdowns, double-dip recessions or more features on expenses, rates or the like.

In the problem we consider words drawn from a linear-sortable alphabet $\Sigma$ of integers. Two words $u$ and $v$ of the same length over $\Sigma$ are said to be order-equivalent written $u \approx v$, if $$u[i] \lt u[j]\Longleftrightarrow v[i] \lt v[j]$$ for all pairs of positions $i,j$ on the words.

The order-preserving pattern-matching problem is naturally defined as follows: given a pattern $x\in\Sigma^*$ and a text $y\in\Sigma^*$, check if $x$ is order-equivalent to some factor of $y$.

For simplicity we assume that letters in each considered word are pairwise distinct (words are permutations of their set of letters).

Design a linear-time algorithm for the order-preserving pattern-matching.
Design a notion of border table adequate to the problem.

References

  • S. Cho, J. C. Na, K. Park, and J. S. Sim. A fast algorithm for orderpreserving pattern matching. Inf. Process. Lett., 115(2):397-402, 2015.
  • M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, A. Langiu, S. P. Pissis, J. Radoszewski, W. Rytter, and T. Walen. Order-preserving indexing. Theor. Comput. Sci., 638:122-135, 2016.
  • P. Gawrychowski and P. Uznanski. Order-preserving pattern matching with k mismatches. In A. S. Kulikov, S. O. Kuznetsov, and P. A. Pevzner, editors, Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings, volume 8486 of Lecture Notes in Computer Science, pages 130-139. Springer, 2014.
  • M. M. Hasan, A. S. M. S. Islam, M. S. Rahman, and M. S. Rahman. Order preserving pattern matching revisited. Pattern Recognition Letters, 55:15-21, 2015.
  • J. Kim, P. Eades, R. Fleischer, S. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, and T. Tokuyama. Order-preserving matching. Theor. Comput. Sci., 525:68-79, 2014.
  • M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, and T. Walen. A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett., 113(12):430-433, 2013.