TY  - JOUR
T1  - An Order-Preserving Pattern Matching Algorithm with Three Partitions
AU  - Kang, Seokchul 
AU  - Na, Joong Chae 
AU  - Sim, Jeong Seop 
JO  - Journal of KIISE, JOK
PY  - 2025
DA  - 2025/1/14
DO  - 10.5626/JOK.2025.52.11.901
KW  - string algorithm
KW  - pattern matching
KW  - order-isomorphism
KW  - order-preserving pattern matching
KW  - partitioned order-isomorphism
KW  - order-preserving pattern matching with partition
AB  - 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.