Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching

Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of pattern P in text T. Unlike the exact matching problem, order-preserving pattern matching considers the relative order of elements, rather than their exact values. In this paper, we propose the first parallel algorithm for the OPPM problem. Our algorithm is based on the “duel-and-sweep” algorithm. For a pattern of length m and a text of length n, our algorithm runs in \(O(\log ^ 3 m)\) time and \(O(n \log ^ 3 m)\) work on the Priority CRCW PRAM.