CLR cover

Additional Problem 6: Idempotent Equivalence (Preliminary version)

Assume we have a finite alphabet $\Sigma$ and there is an idempotent equivalence $xx\approx x$ between any two words in $\Sigma^+$. This equivalence means that any word or any factor $x$ can be replaced by $xx$ and $xx$ can be replaced by $x$. Such replacements imply an equivalence relation $\approx$ between words.

For a given alphabet the number of equivalence classes is finite, but grows considerably. For alphabets of sizes 1,2,3,4,5 the number of equivalence classes is respectively 1,2,7,160,332381.

Let $alpha(u)$ be the set of all letters appearing in $u$. With each $u\in A^*$ we associate a (characteristic) quadruple $\Psi(u)=(p,a,b,q)$, where $a,b\in \Sigma$, $pa$ is a shortest prefix and $bq$ is a shortest suffix of $u$ such that $alpha(pa)=alpha(bq)=alpha(u)$.

We refer to the classical book of Lothaire for a proof of the following fact. We must assume here it is valid.

Lemma (Equivalence Criterion

Assume $\Psi(u)\;=\;(p,a,b,q),\ \ \Psi(v)\;=\;(p',a',b',q')$. Then, $$u\ \approx\ v\ \Leftrightarrow \ (\,p \approx p'\, \wedge\, a=a'\, \wedge\, b=b'\, \wedge \, q \approx q'\,). $$

We assume that the above lemma is valid and we are interested in an efficient algorithmic implentation of the lemma.

Assume integer alphabet (sortable in linear time). Show how to check if $x\approx y$ in $(n\cdot |\Sigma|)$ time, where $n=|x|+|y|$.

References