License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2022.28
URN: urn:nbn:de:0030-drops-161552
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16155/
Go to the corresponding LIPIcs Volume Portal

Jargalsaikhan, Davaajav ; Hendrian, Diptarama ; Yoshinaka, Ryo ; Shinohara, Ayumi

Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations

pdf-format:
LIPIcs-CPM-2022-28.pdf (0.9 MB)

Abstract

Given a text and a pattern over an alphabet, the pattern matching problem searches for all occurrences of the pattern in the text. An equivalence relation ≈ is a substring consistent equivalence relation (SCER), if for two strings X and Y, X ≈ Y implies |X| = |Y| and X[i:j] ≈ Y[i:j] for all 1 ≤ i ≤ j ≤ |X|. In this paper, we propose an efficient parallel algorithm for pattern matching under any SCER using the "duel-and-sweep" paradigm. For a pattern of length m and a text of length n, our algorithm runs in O(ξ_m^t log³ m) time and O(ξ_m^w ⋅ n log² m) work, with O(τ_n^t + ξ_m^t log² m) time and O(τ_n^w + ξ_m^w ⋅ m log² m) work preprocessing on the Priority Concurrent Read Concurrent Write Parallel Random-Access Machines (P-CRCW PRAM), where τ_n^t, τ_n^w, ξ_m^t, and ξ_m^w are parameters dependent on SCERs, which are often linear in n and m, respectively.

BibTeX - Entry

@InProceedings{jargalsaikhan_et_al:LIPIcs.CPM.2022.28,
  author =	{Jargalsaikhan, Davaajav and Hendrian, Diptarama and Yoshinaka, Ryo and Shinohara, Ayumi},
  title =	{{Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16155},
  URN =		{urn:nbn:de:0030-drops-161552},
  doi =		{10.4230/LIPIcs.CPM.2022.28},
  annote =	{Keywords: parallel algorithm, substring consistent equivalence relation, pattern matching}
}

Keywords: parallel algorithm, substring consistent equivalence relation, pattern matching
Collection: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI