# Efficiently Testing Simon's Congruence

arXiv: https://arxiv.org/abs/2005.01112 · HTML: https://mlsanity.com/paper/2005.01112/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2020.

## Built on by (most cited first, 3 of 3)

- [Scattered Factor Universality -- The Power of the Remainder](https://mlsanity.com/paper/2104.09063/) (2021)
- [α-β-Factorization and the Binary Case of Simon's Congruence](https://mlsanity.com/paper/2306.14192/) (2023)
- [Directed Regular and Context-Free Languages](https://mlsanity.com/paper/2401.07106/) (2024)

## Abstract (arXiv)

Simon's congruence ~k is defined as follows: two words are ~k-equivalent if they have the same set of subsequences of length at most k. We propose an algorithm which computes, given two words s and t, the largest k for which s~k t. Our algorithm runs in linear time O(|s|+|t|) when the input words are over the integer alphabet 1,ldots,|s|+|t| (or other alphabets which can be sorted in linear time). This approach leads to an optimal algorithm in the case of general alphabets as well. Our results are based on a novel combinatorial approach and a series of efficient data structures.