CLR cover

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).

Short square

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.