Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem

Kyung Bin Park, Youngho Kim, Joong Cha Na, Jeong Seop Sim

http://doi.org/10.5626/JOK.2022.49.8.585

Two strings of the same length are order-isomorphic if the relative orders of their characters are the same. Given text T of length n and pattern P of length m, the order-preserving pattern matching problem is to find all substrings of T that are order-isomorphic to P. Order-preserving pattern matching can be used to analyze time-series data such as stock indices and melodies. In this paper, we defined the k-scaled order-preserving pattern matching problem and proposed an O(n+mlogm)-time algorithm for the problem. We also proposed a parallel algorithm for the problem, which runs in O(m+k) time using O(n+m) threads.