## Example

\(
\newcommand{\E}{E}%
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)

For the system of equations
$$\E = \{(2,3,1),\, (0,3,3),\, (3,5,3)\},$$
the generic solution $\Psi(E,8)$ is $w=\sa{abaababa}$.
Indeed, $w[2]=w[3]=\sa{a}$, $w[0\dd 2]=w[3\dd 5]=\sa{aba}$ and
$w[3\dd 5]=w[5\dd 7]=\sa{aba}$.
In other words, we have an equivalence on the set of positions
on $w$ comprising two equivalence classes $\{0,2,3,5,7\}$ and $\{1,4,6\}$.
It is the finest equivalence satisfying the equations in $\E$.
Note that $\Psi(E,11)=\sa{abaababacde}$.

#
Problem 67: Generic Words of Factor Equations

The problem deals with an algorithm to build words from factor equations.
A *factor equation* is of the form $w[p\dd q] = w[p'\dd q']$ and has
length $q-p+1$.
In short, the equation is written as a triple $(p,p',q-p+1)$.

We say that a word $w$ of length $n$ is a *{solution* to a system of
factor equations $\E$ if it satisfies each equation of the system.
We are interested in *generic* solutions containing the largest number of
different letters.
Such a solution of length $n$ can be used to describe all
other solutions of the system.
It is denoted by $\Psi(\E,n)$ and defined up to a renaming of letters.

Describe how to build a generic solution $\Psi(\E,n)$ for a given system of
factor equations $\E$ in time $O((n+m)\log n)$, where $m=|\E|$.

Use spanning forests to represent sets of equivalent positions.

## References

P. Gawrychowski, T. Kociumaka, J. Radoszewski, W. Rytter, and
T. Walen. Universal reconstruction of a string. In F. Dehne, J. Sack,
and U. Stege, editors, *Algorithms and Data Structures - 14th International
Symposium, WADS 2015, Victoria, BC, Canada, August 5-7,
2015. Proceedings*, volume 9214 of Lecture Notes in Computer Science,
pages 386-397. Springer, 2015.