Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm

Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of the pattern in the text. Unlike exact matching, order-preserving pattern matching (OPPM) considers the relative order of elements, rather than their exact values. In this paper, we propose efficient algorithms for the OPPM problem using the “duel-and-sweep” paradigm. For a pattern of length m and a text of length n, our serial algorithm runs in \(O(n + m\log m)\) $O(n+mlogm)$ time, and our parallel algorithm runs in \(O(\log ^2 m)\) $O({log}^{2}m)$ time and \(O(n \log ^2 m)\) $O(n{log}^{2}m)$ work with \(O(\log m)\) $O(logm)$ time and \(O(m \log m)\) $O(mlogm)$ work pattern preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM).