@bibtex{2005.01112,
    Abstract = {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(|s|+|t|)$ when the input words are over the integer alphabet $\{1,{\l}dots,|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.},
    Author = {Gawrychowski, Pawel and Kosche, Maria and Koss, Tore and Manea, Florin and Siemer, Stefan},
    EPrint = {arXiv:2005.01112},
    EPrintType = {arXiv},
    File = {2005.01112 - m.pdf},
    Title = {{E}fficiently {T}esting {S}imon's {C}ongruence},
    URL = {http://arxiv.org/abs/2005.01112},
    Year = {2020},
    bdsk-url-1 = {http://arxiv.org/abs/2005.01112},
    bdsk-url-2 = {https://doi.org/10.4230/LIPIcs.STACS.2021.34},
    date-added = {2021-03-17 16:48:21 +0100},
    date-modified = {2021-03-17 16:48:22 +0100},
    doi = {10.4230/LIPIcs.STACS.2021.34}
}

@bibtex{2005.01112, Abstract = {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(|s|+|t|)$ when the input words are over the integer alphabet ${1,{\l}dots,|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.}, Author = {Gawrychowski, Pawel and Kosche, Maria and Koss, Tore and Manea, Florin and Siemer, Stefan}, EPrint = {arXiv:2005.01112}, EPrintType = {arXiv}, File = {2005.01112 - m.pdf}, Title = {{E}fficiently {T}esting {S}imon's {C}ongruence}, URL = {http://arxiv.org/abs/2005.01112}, Year = {2020}, bdsk-url-1 = {http://arxiv.org/abs/2005.01112}, bdsk-url-2 = {https://doi.org/10.4230/LIPIcs.STACS.2021.34}, date-added = {2021-03-17 16:48:21 +0100}, date-modified = {2021-03-17 16:48:22 +0100}, doi = {10.4230/LIPIcs.STACS.2021.34} }