Problem 77: Anchored squares

$ \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.

125 Problems in Text Algorithms

Problem 77: Anchored squares

References