Document Open Access Logo

Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2022.28.pdf
  • Filesize: 0.9 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • parallel algorithm
  • substring consistent equivalence relation
  • pattern matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CPM.2022.28

Author Details

Davaajav Jargalsaikhan
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Diptarama Hendrian
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Ryo Yoshinaka
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Ayumi Shinohara
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan

Funding

  • Hendrian, Diptarama: JSPS KAKENHI Grant Number JP19K20208
  • Yoshinaka, Ryo: JSPS KAKENHI Grant Numbers JP18K11150 and JP20H05703
  • Shinohara, Ayumi: JSPS KAKENHI Grant Number JP21K11745

References

  1. Amihood Amir, Yonatan Aumann, Moshe Lewenstein, and Ely Porat. Function matching. SIAM Journal on Computing, 35(5):1007-1022, 2006. Google Scholar
  2. Amihood Amir, Gary Benson, and Martin Farach. An alphabet independent approach to two-dimensional pattern matching. SIAM Journal on Computing, 23(2):313-323, 1994. Google Scholar
  3. Amihood Amir and Eitan Kondratovsky. Sufficient conditions for efficient indexing under different matchings. In Proceedings of 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  4. Brenda S. Baker. Parameterized pattern matching: Algorithms and applications. Journal of computer and system sciences, 52(1):28-42, 1996. Google Scholar
  5. Omer Berkman, Baruch Schieber, and Uzi Vishkin. Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. Journal of Algorithms, 14(3):344-370, 1993. Google Scholar
  6. Ayelet Butman, Revital Eres, and Gad M. Landau. Scaled and permuted string matching. Information processing letters, 92(6):293-297, 2004. Google Scholar
  7. Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. Searching for jumbled patterns in strings. In Proceedings of the Prague Stringology Conference 2009, pages 105-117, 2009. Google Scholar
  8. Richard Cole, Carmit Hazay, Moshe Lewenstein, and Dekel Tsur. Two-dimensional parameterized matching. ACM Transactions on Algorithms (TALG), 11(2):12, 2014. Google Scholar
  9. Diptarama Hendrian. Generalized dictionary matching under substring consistent equivalence relations. In Proceedings of the 14th International Workshop on Algorithms and Computation, pages 120-132, 2020. Google Scholar
  10. Joseph JáJá. An introduction to parallel algorithms, volume 17. Addison-Wesley Reading, 1992. Google Scholar
  11. Davaajav Jargalsaikhan, Diptarama, Yohei Ueki, Ryo Yoshinaka, and Ayumi Shinohara. Duel and sweep algorithm for order-preserving pattern matching. In Proceesings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018), pages 624-635, 2018. Google Scholar
  12. Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Parallel duel-and-sweep algorithm for the order-preserving pattern matching. In Proceesings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), pages 211-222, 2020. Google Scholar
  13. Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Computing covers under substring consistent equivalence relations. In Proceedings of the 27th International Symposium on String Processing and Information Retrieval, pages 131-146, 2020. Google Scholar
  14. Jinil Kim, Peter Eades, Rudolf Fleischer, Seok-Hee Hong, Costas S. Iliopoulos, Kunsoo Park, Simon J. Puglisi, and Takeshi Tokuyama. Order-preserving matching. Theoretical Computer Science, 525:68-79, 2014. Google Scholar
  15. Donald E. Knuth, James H. Morris, Jr, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM journal on computing, 6(2):323-350, 1977. Google Scholar
  16. Marcin Kubica, Tomasz Kulczyński, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. A linear time algorithm for consecutive permutation pattern matching. Information Processing Letters, 113(12):430-433, 2013. Google Scholar
  17. Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Generalized pattern matching and periodicity under substring consistent equivalence relations. Theoretical Computer Science, 656:225-233, 2016. Google Scholar
  18. Sung Gwan Park, Amihood Amir, Gad M. Landau, and Kunsoo Park. Cartesian tree matching and indexing. In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, pages 16:1-16:14, 2019. Google Scholar
  19. Uzi Vishkin. Optimal parallel pattern matching in strings. In Proceedings of the 12th International Colloquium on Automata, Languages, and Programming, pages 497-508, 1985. Google Scholar
  20. Uzi Vishkin. Deterministic sampling - a new technique for fast pattern matching. SIAM Journal on Computing, 20(1):22-40, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact