CLR cover

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.