Pattern Mining Under Simon’s Congruence

Contribution

Solving the pattern mining problem for Simon’s congruence.

Abstract

Given two strings u and v and an integer k, we say u and v are Simon’s congruent with respect to k if they have the same set of subsequences of length at most k. We study the complete pattern mining problem for Simon’s congruence, where the problem is to find the substrings of a given text T that maximizes the number of congruent substrings of the text, for each possible value of k. We design new data structures that capture the equivalence classes with respect to ∼k for substrings of the text. We then propose an O(|T|^2 log^2 |T|)-time algorithm for fixed-sized alphabets using the new data structures.

Recommended citation:

Sungmin Kim and Yo-Sub Han. “Pattern Mining Under Simon’s Congruence.” International Conference on Developments in Language Theory (DLT), 2025, to appear.