Efficiently Testing Simon's Congruence

Simon’s congruence ${\sim }_k$ is defined as follows: two words are ${\sim }_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{\sim }_{k}t$. Our algorithm runs in linear time $O(\mathrm{\mid }s\mathrm{\mid }+\mathrm{\mid }t\mathrm{\mid })$ when the input words are over the integer alphabet $\{1,\dots ,\mathrm{\mid }s\mathrm{\mid }+\mathrm{\mid }t\mathrm{\mid }\}$ (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.