Proofs: Generalized suffix automaton

The insertion with the extra check builds the generalized suffix automaton full

This proof shows: correctness, termination, time.worst.

Notation. Let $W = (W_0, \ldots, W_{r})$ be a list of strings, positions 0-based. For a nonempty string $u$, $\mathrm{end}_W(u)$ is the set of pairs $(k, e)$ such that $u$ is a suffix of $W_k[0 \ldots e]$; $u$ is a substring of $W$ if this set is nonempty. Two substrings are equivalent if they have the same end set. The generalized suffix automaton $A(W)$ has a root for the empty string and one state for each class; $len(v)$ is the length of the longest string of $v$; $link(v)$ is the class of the longest suffix of the longest string of $v$ that is not in $v$ (the root if there is none); and $\delta(v, c)$ is the class of $uc$ for any $u \in v$, defined when $uc$ is a substring.

Lemma 1 (classes). (a) If $u$ is a suffix of $z$ and both are substrings, then $\mathrm{end}(z) \subseteq \mathrm{end}(u)$. (b) Each class consists of the suffixes of its longest string $z$ with lengths in an interval $(len(link(v)), len(z)]$. (c) $\delta$ is well defined. (d) A prefix $W_k[0 \ldots e]$ is the longest string of its class.

Proof. (a) is clear. (b) If $u$ and $z$ are in one class with $|u| \le |z|$, take an end $(k, e)$ of both: both are suffixes of $W_k[0 \ldots e]$, so $u$ is a suffix of $z$; and any $y$ between them in length that is a suffix of $z$ is in the class, by (a) on both sides. (c) If $\mathrm{end}(u) = \mathrm{end}(u')$, then $\mathrm{end}(uc) = \{(k, e+1) : (k, e) \in \mathrm{end}(u),\ W_k[e+1] = c\} = \mathrm{end}(u'c)$. (d) A string longer than $e + 1$ cannot end at $(k, e)$. $\square$

The step. Suppose the structure is $A(W)$, where the last string of $W$ is the prefix $x = W_r[0 \ldots e]$ (possibly empty, with $e = -1$), and $last$ is the class of $x$ (the root if $x$ is empty). Let $W'$ be $W$ with $W_r$ extended by $c$. Then $\mathrm{end}_{W'}(u) = \mathrm{end}_W(u) \cup \{(r, e+1)\}$ if $u$ is a suffix of $xc$, and $\mathrm{end}_{W'}(u) = \mathrm{end}_W(u)$ otherwise. Let $t$ be the length of the longest suffix $w$ of $xc$ that is a substring of $W$ ($t = 0$ and $w$ empty if there is none).

Lemma 2 (what changes). (i) The suffixes of $xc$ longer than $t$ form one new class with end set $\{(r, e+1)\}$, if $t < |x| + 1$. (ii) Among the old classes, only the class $q$ of $w$ can split, and it splits if and only if $len(q) > t$: into the strings of length greater than $t$, with the old end set, and those of length at most $t$, with the new end. (iii) Every other old class keeps its strings.

Proof. (i) These suffixes are new substrings, and each ends only at $(r, e+1)$. (ii, iii) A class with no suffix of $xc$ keeps its end set. Let $y$ be a suffix of $xc$ of length $j \le t$, with $z$ the longest string of its class. Take an end of $w$; it is also an end of $y$, so of $z$, so $z$ and $w$ are suffixes of one prefix. If $|z| \le t$, $z$ is a suffix of $w$, and by Lemma 1(b) the whole class of $y$ consists of suffixes of $xc$, which all gain the same end. If $|z| > t$, then $w$ is a suffix of $z$ of length between $j$ and $|z|$, so $w$ is in the class of $y$; that is the class $q$. In $q$, the strings of length at most $t$ are suffixes of $xc$, and the longer ones are not, since they are not suffixes of $w$ and $w$ is the longest old suffix of $xc$. $\square$

Lemma 3 (the clone keeps the transitions). If $q$ splits into $q$ (long part) and $q'$ (short part), then $\delta_{W'}(q', a) = \delta_W(q, a)$ and $\delta_{W'}(q, a) = \delta_W(q, a)$ for every symbol $a$, and the targets are old classes that do not split.

Proof. For $u \in q'$, a pair $(r, e+2)$ cannot be an end of $ua$, since $W'_r$ has length $e + 2$. So $\mathrm{end}_{W'}(ua) = \mathrm{end}_W(ua)$, the shifted old ends of $u$, which are the shifted ends of all of $q$. The target class contains strings of length $len(q) + 1$ or less that are not suffixes of $xc$ ending at the new place, so it is not $q$, and by Lemma 2 it keeps its strings. $\square$

Theorem 1 (correctness). GSA-EXTEND$(last, c)$ turns $A(W)$ into $A(W')$ and returns the class of $xc$.

Proof. By Lemma 1(d), $len(last) = |x|$. The transitions that change are $\delta(v, c)$ for the classes $v$ whose strings $u$ have $uc$ in a new or split class: the suffixes $u$ of $x$ with $|u| \ge t$ (whose $uc$ is new), and those with $len(link(q)) \le |u| \le t - 1$ when $q$ splits (whose $uc$ moves to $q'$). The suffix links change only for the new class, for $q$ and for $q'$: a class $v$ with $link(v) = q$ points to the longest string of $q$, which stays in the long part. The classes of the suffixes of $x$ are the states on the suffix-link path from $last$, by Lemma 1(b) applied to the prefix $x$.

Case 1: $\delta(last, c)$ exists (lines L1 to L3). Then $xc$ is a substring of $W$, so $t = |x| + 1$, no class is new, and $q = \delta(last, c)$ is the class of $xc$. If $len(q) = t$, nothing splits and no transition or link changes, so $q$ is returned correctly. Otherwise SPLIT makes the clone with $len = len(last) + 1 = t$, the old link of $q$ and the transitions of $q$ (Lemma 3), moves $\delta(p, c)$ from $q$ to the clone on the path from $last$ while it pointed to $q$, which are the classes with $len(link(q)) \le |u| \le t - 1$, and sets $link(q)$ to the clone. The clone is the class of $xc$, and it is returned.

Case 2: no transition (lines L4 to L9). Then $t \le |x|$ and the new class $cur$ has $len = |x| + 1$. Line L5 walks the path from $last$ and sets $\delta(p, c) = cur$ while $p$ has no transition on $c$; these are the classes whose strings $u$ have $|u| \ge t$, since $\delta(p, c)$ exists for all members of a class or for none. If the walk passes the root, no suffix of $xc$ was a substring, $t = 0$, and $link(cur)$ is the root (L6). Otherwise the walk stops at the class $p$ of the suffix of $x$ of length $t - 1$, and $len(p) = t - 1$, since a longer member $z$ of $p$ would give an old suffix $zc$ of $xc$ longer than $t$. So $q = \delta(p, c)$ is the class of $w$. If $len(q) = len(p) + 1 = t$, nothing splits and $link(cur) = q$ (L7). Otherwise SPLIT with $len(p) + 1 = t$ splits $q$ as in Case 1, starting the walk at $p$, and $link(cur)$ is the clone (L8). The new class is the class of $xc$ and is returned (L9). $\square$

Theorem 2 (build). Inserting the strings one by one, each from the root, gives $A(S_0, \ldots, S_{m-1})$.

Proof. $A$ of the empty list, and of a list that ends with an empty string, is the root alone. Starting a new string adds an empty last string, which changes no end set, and $last$ = root is its class. Theorem 1 then applies at each symbol. $\square$

Theorem 3 (time). For a constant alphabet, the build takes $O(N)$ time.

Proof. Each call creates at most two states, so there are $O(N)$ states, and the work outside the loops of L5 and L11 is $O(1)$ per call. For one string, Blumer et al. bound the total work of these loops by $O(n)$ with a potential: the number of steps of the loop of L5 is paid by the drop in the depth, in the suffix-link tree, of the link of the state returned, compared with the depth of $last$, and the redirect loop of L11 by the same drop for the clone. The same accounting holds here within one string, and starting a new string at the root sets the depth to 0, which only lowers the potential. So the total is $O(N)$. With a transition map of $\sigma$ symbols, each transition access adds a factor of $O(\log \sigma)$ for sorted maps, or $O(1)$ expected time for hashing. $\blacksquare$