Simon’s Congruence Pattern Matching

Sungmin Kim, Sang Ki Ko, Yo Sub Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

Abstract

Testing Simon’s congruence asks whether two strings have the same set of subsequences of length no greater than a given integer. In the light of the recent discovery of an optimal linear algorithm for testing Simon’s congruence, we solve the Simon’s congruence pattern matching problem. The problem requires finding all substrings of a text that are congruent to a pattern under the Simon’s congruence. Our algorithm efficiently solves the problem in linear time in the length of the text by reusing results from previous computations with the help of new data structures called X-trees and Y-trees. Moreover, we define and solve variants of the Simon’s congruence pattern matching problem. They require finding the longest and shortest substring of the text as well as the shortest subsequence of the text which is congruent to the pattern under the Simon’s congruence. Two more variants which ask for the longest congruent subsequence of the text and optimizing the pattern matching problem are left as open problems.

Original languageEnglish
Title of host publication33rd International Symposium on Algorithms and Computation, ISAAC 2022
EditorsSang Won Bae, Heejin Park
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772587
DOIs
Publication statusPublished - 2022 Dec 1
Event33rd International Symposium on Algorithms and Computation, ISAAC 2022 - Virtual, Online, Korea, Republic of
Duration: 2022 Dec 192022 Dec 21

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume248
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Algorithms and Computation, ISAAC 2022
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period22/12/1922/12/21

Bibliographical note

Publisher Copyright:
© Sungmin Kim, Sang-Ki Ko, and Yo-Sub Han.

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Simon’s Congruence Pattern Matching'. Together they form a unique fingerprint.

Cite this