Efficiently Testing Simon’s Congruence

Simon’s congruence is defined as follows: two words are -equivalent if they have the same set of subsequences of length at most. We propose an algorithm which computes, given two words and, the largest for which. Our algorithm runs in linear time when the input words are over the integer alphabet (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.

Authors

• Florin Manea

Keywords

No keywords are indexed for this paper.