Example
\(
\def\sa#1{\tt{#1}}
\def\lrep{\mathit{\ell rep}}
\def\per{\mathit{per}}
\def\ms{\mathit{ms}}
\def\MS{\mathrm{MaxSuffix}}
\def\MSP{\mathrm{MaxSuffixPos}}
\def\eA{A^*}
\def\dd{\dot{}\dot{}}
\)
For the word $\sa{baabababba}$ of period
$8$ we have $\lrep(1)=|\sa{aab}|=3$, $\lrep(6)=|\sa{ab}|=2$,
$\lrep(10)=|\sa{a}|=1$ and $\lrep(7)=|\sa{bbaababa}|=8$.
Applied to $x=\sa{baabababba}$, $\MSP(\leq, x)=7$ is a critical position
and, for this example, $\MSP(\leq^{-1}, x)=1$ is not.
|
Problem 41: Critical Position of a Word
|
|
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.
