Simon's congruence pattern matching

Sungmin Kim, Sang Ki Ko, Yo Sub Han

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

The Simon's congruence problem is to determine whether or not two strings have the same set of subsequences of length no greater than a given integer, and the problem can be answered in linear time. We consider the Simon's congruence pattern matching problem that looks for all substrings of a text that are congruent to a pattern under the Simon's congruence. We propose a linear time algorithm by reusing results from previous computations with the help of new data structures called X-trees and Y-trees. Moreover, we investigate several variants of the problem such as identifying the shortest substring or subsequence of the text that is congruent to the pattern under the Simon's congruence, or finding frequent matchings. We design efficient algorithms for these problems. We conclude the paper with two open problems: finding the longest congruent subsequence and optimizing the pattern matching problem.

Original languageEnglish
Article number114478
JournalTheoretical Computer Science
Volume994
DOIs
Publication statusPublished - 2024 May 1

Bibliographical note

Publisher Copyright:
© 2024 Elsevier B.V.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Simon's congruence pattern matching'. Together they form a unique fingerprint.

Cite this