CLR cover
Previous problem

Problem 116: Period-Equivalent Binary Words

Next problem

Two words are said to be period equivalent if they have the same set of periods or equivalently have the same length and the same set of border lengths.

The goal of the problem is to show that a set of periods of a word can be realised by a binary word.

Let $w$ be a word over an arbitrarily large alphabet. Show how to construct in linear time a binary word $x$ period equivalent to~$w$.
Consider border lengths instead of periods.

References

  • M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.
  • W. Rytter. Two fast constructions of compact representations of binary words with given set of periods. Theor. Comput. Sci., 656:180-187, 2016.