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.

125 Problems in Text Algorithms

Example

Problem 67: Generic Words of Factor Equations

References