TATA = (TA)² - Text Algorithms: Tables and Automata

• Tables
  • Border table
  • Strict border table
  • Prefix table
  • Suffix table
  • Good-suffix table
  • Last occurrence table
  • Suffix array
• Automata
  • String Matching automaton
  • Subsequence automaton

Example

Strict Border Table

Strict Border Table

The strict-border table or best prefix 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$.

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

The strict-border table can be computed in $O(|x|)$ time by the following algorithm.

    \begin{algorithmic}
   \STATE $stbord[0]\leftarrow -1$
   \STATE $i\leftarrow 0$
   \FOR{$j\leftarrow 1$ \TO $m-1$}
      \IF{$x[i] = x[j]$}
         \STATE $stbord[j]\leftarrow stbord[i]$
      \ELSE
         \STATE $stbord[j]\leftarrow i$
         \REPEAT
            \STATE $i\leftarrow stbord[i]$
         \UNTIL{$i \lt 0$ \OR $x[i] = x[j]$}
      \ENDIF
      \STATE $i\leftarrow i+1$
   \ENDFOR
   \STATE $stbord[m]\leftarrow i$
   \RETURN{$stbord$}
    \end{algorithmic}

The strict border table is used in the Knuth-Morris-Pratt exact string matching algorithm.