DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.60

Simon’s Congruence Pattern Matching

Authors: Sungmin Kim, Sang-Ki Ko, and Yo-Sub Han

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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.

Cite as

Sungmin Kim, Sang-Ki Ko, and Yo-Sub Han. Simon’s Congruence Pattern Matching. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2022.60,
  author =	{Kim, Sungmin and Ko, Sang-Ki and Han, Yo-Sub},
  title =	{{Simon’s Congruence Pattern Matching}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.60},
  URN =		{urn:nbn:de:0030-drops-173456},
  doi =		{10.4230/LIPIcs.ISAAC.2022.60},
  annote =	{Keywords: pattern matching, Simon’s congruence, string algorithm, data structure}
}

Search Results

Documents authored by Kim, Sungmin

Simon’s Congruence Pattern Matching

Abstract

Cite as

Thanks for your feedback!

Could not send message