Duel and Sweep Algorithm for Order-Preserving Pattern Matching
The 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018),
Lecture Notes in Computer Science Vol.10706, pp.624-635
(2018), [peer-reviewed]
Event Date:
January 29-February 2, 2018
Abstract / 概要
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 t han their real values. In this paper, we propose an efficient algorithm for the OPPM problem using the “duel-and-sweep” paradigm. For a pattern of length $m$ and a text of length $n$, our algorithm runs in $O(n + m \log{m})$ time in general, and in $O(n + m)$ time under an assumption that the characters in a string can be sorted in linear time with respect to the string size. We also perform experiments and show that our algorithm is faster than the KMP-based algorithm.