Seokchul Kang  Joong Chae Na  Jeong Seop Sim

10.5626/JOK.2025.52.11.901

string algorithm Pattern matching order-isomorphism order-preserving pattern matching partitioned order-isomorphism order-preserving pattern matching with partition

Two strings of equal length are considered order-isomorphic if they have identical relative orders at every position. The order-preserving pattern matching problem seeks to identify all substrings in a text T that are order-isomorphic to a given pattern P. Additionally, if two strings of equal length can be split at a certain position such that the resulting substrings are order-isomorphic to each other, they are termed partitioned order-isomorphic. The order-preserving pattern matching with partition problem aims to find all substrings in a text T that are partitioned order-isomorphic to a specified pattern P. In this paper, we introduce the order-preserving pattern matching with 3-partition problem and present an algorithm that solves it in O(nm² + m² log m) time. We also perform experiments on various time series datasets to compare the number of matches and the runtime performance of the order-preserving pattern matching, partitioned order-preserving pattern matching, and order-preserving pattern matching with 3-partition algorithms.