CLR cover
Previous problem

Problem 41: Critical Position of a Word

Next problem

The existence of critical positions on a word is a wonderful tool for combinatorial analyses and also for the design of text algorithms. One of its striking application is the two-way string matching implemented in some C libraries.

Let $x$ be a non-empty word and $\lrep(i)$ denote the local period at $i$ on $x$, $i=0,\dots,|x|$, length of the shortest non-empty word $w$ that is $$\mbox{suffix of }\eA x[0\dd i-1] \;\mbox{ and prefix of }\; x[i\dd |x|-1]\eA.$$

In lay terms this roughly means the shortest non-empty square $ww$ centred at position $i$ has period $\lrep(i)$. Some squares overflow the word to the right, to the left or to both.

Note that $\lrep(i) \leq \per(x)$ for any $i$. If $\lrep(i)=\per(x)$, $i$ is called a critical position. When $x=u\cdot v$ its factorisation is said to be critical if $\lrep(|u|) = \per(x)$.

Let $\MS(\leq, x)$ and $\ms=\MSP(\leq, x)$ be the respective greatest suffix of $x$ and its position according to the alphabet ordering $\leq$.

Let $x=yz$ where $z=\MS(\leq, x)$. Show that $|y| \lt \per(x)$, that is $\MSP(\leq, x)\lt\per(x)$.

Algorithm CriticalPos computes a critical position in linear time and constant extra space following Problems 38 and 40.

CriticalPos$(x \textrm{ non-empty word})$
    \begin{algorithmic}
  \STATE $i\leftarrow$ MaxSuffixPos$(\leq, x)$
  \STATE $j\leftarrow$ MaxSuffixPos$(\leq^{-1}, x)$
  \RETURN{$\max\{i,j\}$}
    \end{algorithmic}

Show that Algorithm CriticalPos computes a critical position on its non-empty input word.
Note the intersection of the two word orderings is the prefix ordering and use the duality between borders and periods.

References

  • D. Breslauer, R. Grossi, and F. Mignosi. Simple real-time constant-space string matching. Theor. Comput. Sci., 483:2-9, 2013.
  • Y. Césari and M. Vincent. Une caractérisation des mots périodiques. C. R. Acad. Sci., 286:1175, 1978.
  • M. Crochemore and D. Perrin. Two-way string-matching. J. ACM, 38(3):651-675, 1991.
  • 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.-P. Duval. Factorizing words over an ordered alphabet. J. Algorithms, 4(4):363-381, 1983.
  • M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted in 1997.