Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \newcommand{\prefix}{\mathit{prefix}}% $

$\sa{abcdabcda}$ and $\sa{abaaabaaa}$ are period equivalent, since they share the same set of periods $\{4,8,9\}$ although their letters are not in one-to-one correspondence.

Problem 116: Period-Equivalent Binary Words

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.

125 Problems in Text Algorithms

Example

Problem 116: Period-Equivalent Binary Words

References