Duel and sweep algorithm for order-preserving pattern matching

DOI10.1007/978-3-319-73117-9_44MaRDI QIDQ5127200zbMATH OpenOpenAlexFDO

Authors Davaajav Jargalsaikhan, Diptarama, Yohei Ueki, Ryo Yoshinaka, Ayumi Shinohara

Publication date 21 October 2020

Published in SOFSEM 2018: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09438

zbMATH Keywords

duel-and-sweeporder-preserving pattern matching

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Abstract: Given a text $T$ and a pattern $P$ over alphabet $Sigma$, the classic exact matching problem searches for all occurrences of pattern $P$ in text $T$. Unlike exact matching problem, order-preserving pattern matching (OPPM) considers the relative order of elements, rather than their real values. In this paper, we propose an efficient algorithm for OPPM problem using the "duel-and-sweep" paradigm. Our algorithm runs in $O(n+mlogm)$ time in general and $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 that KMP-based algorithm. Last, we introduce the two-dimensional order preserved pattern matching and give a duel and sweep algorithm that runs in $O(n^2)$ time for duel stage and $O(n^{2}m)$ time for sweeping time with $O(m^3)$ preprocessing time.

Recommendations

• Parallel duel-and-sweep algorithm for the order-preserving pattern matching
• A fast algorithm for order-preserving pattern matching
• Efficient algorithms for the order preserving pattern matching problem
• Fast order-preserving pattern matching
• The order-preserving pattern matching problem in practice

Cited in

(3)

• Parallel duel-and-sweep algorithm for the order-preserving pattern matching
• A fast algorithm for order-preserving pattern matching
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm

This page was built for publication: Duel and sweep algorithm for order-preserving pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5127200)