CLR cover
Previous problem

Problem 25: Strict Borders

Next problem
\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\tbord{\mathit{border}} \def\sbord{\mathit{stbord}} \)

When used for searching texts online, the border table of a pattern is better replaced by the notion introduced in this problem. The effect is to improve the behaviour of searches as shown in Problem 26.

The strict-border table of a non-empty word $x$ is defined on the lengths $\ell$, $\ell=0, \dots, |x|$, of its prefixes by: $\sbord[0]=-1$, $\sbord[|x|]=\tbord[|x|]$ and, for $0 \lt \ell \lt |x|$, $\sbord[\ell]$ is the greatest $t$ satisfying

Word $x[0\dd \sbord[\ell]-1]$ is the strict border of prefix $x[0\dd \ell-1]$ of $x$. It exists only if $\sbord[\ell]\neq-1$.

Here are border and strict-border tables of the word $\sa{abaababaaba}$:
$i$ 012345678910
$x[i]$ $\sa{a}$$\sa{b}$$\sa{a}$$\sa{a}$$\sa{b}$$\sa{a}$$\sa{b}$$\sa{a}$$\sa{a}$$\sa{b}$$\sa{a}$
$\ell$ 01234567891011
$\tbord[\ell]$ -100112323456
$\sbord[\ell]$ -10-110-13-110-16

Design a linear-time algorithm computing the table $\sbord$ without using the table $\tbord$ or any other additional table.

References

  • D. E. Knuth, J. H. Morris Jr., and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977.