CLR cover

Problem 66: Word Square-Freeness with DBF

The dictionary of Basic Factors (DBF} in short) is a useful elementary data structure to produce efficient algorithmic solutions to many problems on words. It is used here to test the square-freeness of a word.

The DBF of a word $w$ consists of a logarithmic number of tables $\NAME_k$, $0\leq k \leq \log|w|$. Tables are indexed by positions on $w$ and $\NAME_k[j]$ intends to identify $w[j\dd j+2^k-1]$, factor of length $2^k$ starting at position $j$ on $w$. Identifiers have the following property, for $i\neq j$: $\NAME_k[i]=\NAME_k[j]$ if and only if $$i+2^k-1,j+2^k-1\lt |w| \mbox{ and } w[i\dd i+2^k-1]=w[j\dd j+2^k-1].$$ It is known that the DBF of $w$ can be computed in time $O(|w|\log |w|)$.

To test the square-freeness of $w$, let $\PRED_k$, $0\leq k\lt \log|w|$, denote the table indexed by positions on $w$ and defined by $$\PRED_k[j] = \max\{i\lt j \mid \NAME_k[i]=\NAME_k[j]\}\cup\{-1\}$$ and let $\CAND_w$ denote the set of pairs of positions $(i,2j-i)$ on $w$, candidates for a square occurrence $w[i\dd 2j-i-1]$ in $w$: $$\CAND_w = \{(i,2j-i) \mid 2j-i\leq |w| \mbox{ and } i=\PRED_k[j]\ne -1 \mbox{ for some } k\}.$$

Show that a word $w$ contains a square if $w[p\dd q-1]$ is a square for some $(p,q)\in \CAND_w$. Deduce an algorithm checking if the word $w$ is square-free in time $O(|w|\log |w|)$.

References

  • M. Crochemore, C. S. Iliopoulos, M. Kubica, J. Radoszewski, W. Rytter, K. Stencel, and T. Walen. New simple efficient algorithms computing powers and runs in strings. Discrete Applied Mathematics, 163:258-267, 2014.