Back to Search Start Over

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

Authors :
Jargalsaikhan, Davaajav
Hendrian, Diptarama
Ueki, Yohei
Yoshinaka, Ryo
Shinohara, Ayumi
Source :
Acta Informatica. Dec2024, Vol. 61 Issue 4, p415-444. 30p.
Publication Year :
2024

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 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) time, and our parallel algorithm runs in O (log 2 m) time and O (n log 2 m) work with O (log m) time and O (m log m) work pattern preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM). [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00015903
Volume :
61
Issue :
4
Database :
Academic Search Index
Journal :
Acta Informatica
Publication Type :
Academic Journal
Accession number :
180654855
Full Text :
https://doi.org/10.1007/s00236-024-00464-w