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.

125 Problems in Text Algorithms

Example

Strict Borders

Problem 25: Strict Borders

References

$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