Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\lrep{\mathit{\ell rep}} $

For $x = \sa{baabaababaabaa}$, squares centred at $7$ are $\sa{(abaab)}^2$, $\sa{(ab)}^2$ and the empty square. There is no non-empty square centred at $6$ or $9$, for example.

Here are a few local periods for the above example word: $\lrep(7)=2$ period of $\sa{(ab)}^2$, $\lrep(1)=3$ period of $\sa{(aab)}^2$, $\lrep(6)=8$ period of $\sa{(babaabaa)}^2$ and $\lrep(9)=5$ period of $\sa{(aabab)}^2$.

Problem 85: Short Square and Local Period

The notion of local periods in words provides a more accurate structure of its repetitiveness than its global period. The notion is central to that of critical positions (see Problem 41) and their applications.

Finding the local period at a given position $i$ on a word $x$ is the question of the problem. The local period $\lrep(i)$ is the period of a shortest non-empty square $ww$ centred at position $i$ and possibly overflowing $x$ to the left or to the right (or both).

Show how to compute all non-empty squares centred at a given position $i$ on $x$ in time $O(|x|)$.

If there exists a shortest non-empty square of period $p$ centred at position $i$ on $x$, show how to find it in time $O(p)$.

Double the length of the search area.

Design an algorithm to compute the local period $p$ at position $i$ on $x$ in time $O(p)$.

Mind the situation where there is no square centred at $i$.

References

M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings. Cambridge University Press, 2007. 392 pages.

M. Crochemore and W. Rytter. Text algorithms. Oxford University Press, 1994. 412 pages.

M. Crochemore and W. Rytter. Jewels of Stringology. World Scientific Publishing, Hong-Kong, 2002. 310 pages.

J. Duval, R. Kolpakov, G. Kucherov, T. Lecroq, and A. Lefebvre. Lineartime computation of local periods. Theor. Comput. Sci., 326(1-3):229-240, 2004.

D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997.

B. Smyth. Computing Patterns in Strings. Pearson Education Limited, Harlow, England, 2003. 423 pages.

125 Problems in Text Algorithms

Example

Problem 85: Short Square and Local Period

References