@article{MFC809702,
title = "An Order-Preserving Pattern Matching Algorithm with Three Partitions",
journal = "Journal of KIISE, JOK",
year = "2025",
issn = "2383-630X",
doi = "10.5626/JOK.2025.52.11.901",
author = "Seokchul Kang, Joong Chae Na, Jeong Seop Sim",
keywords = "string algorithm, pattern matching, order-isomorphism, order-preserving pattern matching, partitioned order-isomorphism, order-preserving pattern matching with partition",
abstract = "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."
}