# Problem 25: Strict Borders

$$\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

• $-1\le t \lt \ell$ and
• $(x[0\dd t-1] \mbox{ is a border of } x[0\dd \ell-1] \mbox{ and } x[t]\ne x[\ell]) \mbox{ or } t=-1$.
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$ 0 1 2 3 4 5 6 7 8 9 10 $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$ 0 1 2 3 4 5 6 7 8 9 10 11 $\tbord[\ell]$ -1 0 0 1 1 2 3 2 3 4 5 6 $\sbord[\ell]$ -1 0 -1 1 0 -1 3 -1 1 0 -1 6

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.