Back to Search
Start Over
Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm.
- 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]
- Subjects :
- *PARALLEL algorithms
*BABY strollers
*ALGORITHMS
Subjects
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