CLR cover
Previous problem

Problem 77: Anchored squares

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

When searching, in a divide-and-conquer way, a word for square factor it is natural to look for squares in the product of two square-free words. The problem deals with the latter question and extends to a square-freeness test running in $O(n\log n)$ time on a word of length $n$.

The method based on prefix tables (see Problem 74) achieves the same goal but requires tables of size $O(n)$ while the present solution needs only a few variables in addition to input.

Let $y$ and $z$ be two square-free words. Algorithm Right tests if $yz$ contains a square centred in $z$ only. Other squares in the product can be found symmetrically.

The algorithm examines all possible periods of a square. Given a period $p$ (see picture), it computes the longest common suffix $u'=z[j\dd p-1]$ between $y$ and $z[0\dd p-1]$. Then it checks if $z[0\dd j-1]$ occurs at position $p$ on $z$, scanning $z$ from the right position $k-1$ of the potential square. If it is successful, a square is found.

Right$(y,z \textrm{ non-empty square-free strings})$
    \begin{algorithmic}
\STATE $(p,\mathit{end})\leftarrow (|z|,|z|)$
\WHILE{$p \gt  0$}
        \STATE $j\leftarrow  \min\{q \mid z[q..p-1] \mbox{ suffix of } y\}$
        \IF{$j = 0$}
            \RETURN{True}
        \ENDIF
        \STATE $k\leftarrow p+j$
        \IF{$k \lt \mathit{end}$}
            \STATE $\mathit{end}\leftarrow \min\{q \mid z[q..k-1] \mbox{ suffix of } z[0..j-1]\}$
            \IF{$\mathit{end} = p$}
                \RETURN{True}
            \ENDIF
        \ENDIF
        \STATE $p\leftarrow \max\{j-1,\lfloor p/2 \rfloor\}$
\ENDWHILE
\RETURN{False}
    \end{algorithmic}

Show both that Algorithm Right returns true if and only if the word $yz$ contains a square centred in $z$ and that its running time is $O(|z|)$ with only constant extra space.

In Algorithm Right the role of variable $\mathit{end}$ and instructions at lines 7 and 11 are crucial to get the running time announced in the question. Note that it does not depend on the length of $y$.

References

  • M. Crochemore. Régularités évitables. Thèse d'état, Université de Haute-Normandie, 1983.
  • M. Crochemore. Transducers and repetitions. Theor. Comput. Sci., 45(1):63-86, 1986.
  • M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007. 392 pages.
  • 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.
  • M. Crochemore and W. Rytter. Jewels of Stringology. World Scientific Publishing, Hong-Kong, 2002. 310 pages.
  • J. Fischer and V. Heun. Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In M. Lewenstein and G. Valiente, editors, Combinatorial Pattern Matching, 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006, Proceedings, volume 4009 of Lecture Notes in Computer Science, pages 36-48. Springer, 2006.
  • M. G. Main and R. J. Lorentz. An $O(n \log n)$ algorithm for recognizing repetition. Report CS-79-056, Washington State University, Pullman, 1979.