Proofs: Blumer et al. suffix automaton algorithm

EXTEND turns the suffix automaton of t into that of tc, in amortized constant steps full

This proof shows: correctness, complexity.

We use the pseudocode and the notation of the page. For a text $t$ of length $i$ and a substring $w$, $endpos_t(w)$ is the set of end positions of the occurrences of $w$, with $endpos_t(\varepsilon) = \{0, \ldots, i\}$. A class is a set of substrings with the same end set, and $[w]_t$ is the class of $w$.

Facts on classes. (F1) If $u$ is a suffix of $w$, then $endpos(w) \subseteq endpos(u)$. If two substrings $x$ and $y$ end at a common position, one is a suffix of the other. Hence the strings of a class are the suffixes of its longest string with lengths in an interval, and if $y$ is a substring with $endpos(y) \subseteq endpos(x)$, $\lvert y \rvert \ge \lvert x \rvert$, then $x$ is a suffix of $y$. (F2) $endpos(wa) = \{e + 1 : e \in endpos(w), t_{e+1} = a\}$, so $[wa]$ depends only on $[w]$ and $a$. (F3) If $x$ is the longest suffix of the longest string $y$ of a class $C$ that is not in $C$, then $x$ is the longest string of its class: a longer $x' \in [x]$ would end at each end of $y$ (since $endpos(y) \subseteq endpos(x) = endpos(x')$), so by (F1) $x'$ would be a suffix of $y$ longer than $x$ outside $C$, or $y$ would be a suffix of $x'$ and then all three end sets are equal and $x \in C$.

The invariant (A). For the current text $t$: the states other than 0 are the classes of nonempty substrings, and 0 is the class of $\varepsilon$; $len(v)$ is the length of the longest string of $v$; $link(v)$ is the class of the longest suffix of that string outside $v$; $\delta(v, a) = [wa]$ for $w \in v$ when $wa$ is a substring, and undefined otherwise; $last = [t]$. By (F1) the link path from $last$ visits, in order of decreasing length, classes that together contain each suffix of $t$ once. (A) holds for the empty text.

What changes when $c$ is appended. Let $t' = tc$ and let $s$ be the longest suffix of $t'$ that is a substring of $t$ ($s = \varepsilon$ if there is none). For $w$ a substring of $t'$, $endpos_{t'}(w)$ is $endpos_t(w)$, plus $i + 1$ if $w$ is a suffix of $t'$.

1. The suffixes of $t'$ longer than $s$ are new and end only at $i + 1$: they form one class $C_{new}$, with longest string $t'$ and suffix link $[s]_{t'}$, by (F3) applied in $t'$.
2. The classes of $t$ whose strings are all suffixes of $t'$, or all not, keep the same strings.
3. At most one class of $t$ splits, the class $Q = [s]_t$ when $s$ is not its longest string. Indeed, let $C$ be a class of $t$ with a suffix $x$ of $t'$ and a string $y$ that is not, so $\lvert x \rvert < \lvert y \rvert$ by (F1) and $\lvert x \rvert \le \lvert s \rvert$, so $x$ is a suffix of $s$. Then $y$ ends at each end of $s$; if $\lvert y \rvert \le \lvert s \rvert$, $y$ would be a suffix of $s$ and of $t'$, so $s$ is a suffix of $y$ and $endpos(y) \subseteq endpos(s) \subseteq endpos(x) = endpos(y)$, so $s \in C$. Then $Q$ splits into $Q_{short}$, its strings of length at most $\lvert s \rvert$ (all suffixes of $s$, which gain $i + 1$), and $Q_{long}$, the longer ones.

The walk of line L2. For a state $p$ on the link path of $last$, all its strings $u$ have $uc$ a substring of $t$ or none do, by (F2); and if $uc$ is a substring so is $u'c$ for each suffix $u'$ of $u$. So the walk passes exactly the states of the suffixes $u$ of $t$ for which $uc$ is new, that is $uc \in C_{new}$, and setting $\delta(p, c) = cur$ is the transition of (A) in $t'$. It stops at the state $p$ whose longest string $w$ is the longest suffix of $t$ with $wc$ a substring, so $s = wc$ and $\lvert s \rvert = len(p) + 1$; or it runs off the path, and then $s = \varepsilon$ and line L3 sets $link(cur) = 0$. Line L1 sets $len(cur) = len(last) + 1 = i + 1$, the length of $t'$.

Line L4. Here $q = \delta(p, c) = [s]_t$. If $len(q) = \lvert s \rvert$, then $s$ is the longest string of $q$, all strings of $q$ are suffixes of $s$, and no class splits. The link of $cur$ is $[s] = q$, as item 1 requires. No other state changes its strings, so their lengths, links and transitions stay right; a transition into $C_{new}$ comes from a state of a string $u$ with $uc$ a suffix of $t'$ longer than $s$, which is a state passed by the walk; and $cur$ has no transitions, since its strings end only at the last position.

Lines L5 to L7. If $len(q) > \lvert s \rvert$, $q$ splits. The clone is $Q_{short}$: its longest string is $s$, so its length is $len(p) + 1$; its link is the class of the longest suffix of $s$ below $Q$, which is the old $link(q)$; and $q$ becomes $Q_{long}$, with the same length and the link $Q_{short}$. Transitions out of the two parts: a transition from $q$ never led to $q$ itself, since an end set is not its own shift by one (compare the largest elements), so the targets are classes other than $Q$, which keep their identity, and the targets of $Q_{short}$ and $Q_{long}$ are those of $Q$, by (F2) in $t'$ applied to strings that had the same targets in $t$. So copying the transitions of $q$ to the clone is right. Transitions into $Q$: a state $x$ with $\delta(x, a) = q$ must now go to $Q_{short}$ if its strings $u$ have $ua$ in $Q_{short}$, which means $ua$ is a suffix of $t'$, so $a = c$ and $u$ is a suffix of $t$; so $x$ is on the link path of the old $last$. Along that path, the targets on $c$ are the classes of $uc$ for suffixes $u$ of decreasing length, and the $uc$ in $Q$ have lengths in an interval, so these states are $p$ and its consecutive link ancestors up to the first one whose $c$-transition goes elsewhere. Line L6 redirects exactly these. The link of $cur$ is $[s]_{t'} = Q_{short}$, set at line L7. A state $v$ whose old link was $q$ had as link the longest string of $q$ (by (F3)), which lies in $Q_{long}$, so its link stays $q$. The rest is as in the case of line L4.

So (A) holds for $t'$, and line L8 sets $last = [t']$. By induction, after the whole text the automaton is the automaton of the classes. With the states on the link path from $last$ as accepting states, the automaton accepts the suffixes of $t$, and it is the minimal automaton of this language: two strings $u$ and $v$ are right-equivalent for it if and only if they are both non-substrings or have the same end set, since the strings $z$ with $uz$ a suffix of $t$ are exactly the $t_{e+1} \cdots t_n$ for $e \in endpos(u)$, and these determine $endpos(u)$. So by the Myhill-Nerode theorem the automaton is minimal. (For the language of all substrings, two strings are right-equivalent as soon as their first occurrences end at the same place, so that minimal automaton can have fewer states.) $\square$

The running time. Let $d(v)$ be the number of links from $v$ to state 0. First, for each transition $\delta(x, a) = y$, $d(y) \le d(x) + 1$: fix $w \in x$; each state $z \ne 0$ on the link path of $y$ contains a suffix $u'a$ of $wa$, and $u'$ is a suffix of $w$, so $[u']$ is on the link path of $x$; two different $z$ give different classes $[u']$ by (F2); so the path of $y$ has at most one more state than that of $x$.

Consider a call with $k_2$ iterations of line L2 and $k_6$ of line L6. The state $p$ after line L2 has $d(p) = d(last) - k_2$, and its path is not changed by the call, since only $q$ and the new states get new links and $len(q) > len(p)$. In case L3, $d(cur) = 1$. In case L4, $d(cur) = d(q) + 1 \le d(p) + 2$. In the clone case, the last state redirected in line L6 has depth $d(p) - k_6 + 1$ and a $c$-transition to the clone, so $d(cur) = d(clone) + 1 \le d(p) - k_6 + 3$. In all cases $d(cur) \le d(last) - k_2 - k_6 + 3$. Summing over the $n$ calls, with $d \ge 0$, the total number of iterations of lines L2 and L6 is at most $3n$. With the at most $3n - 4$ transitions copied in line L5, the number of transition operations is $O(n)$, and the time is $O(n)$ times the cost of one transition operation. $\blacksquare$