Why does the construction step of Aho-Corasick take linear time in the number of nodes?

Question

The original paper's analysis of this, as far as I can tell is this:

"THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward."

But it's not at all obvious.

Answer 1

Using for reference, Aho and Corasick, Efficient string matching: an aid to bibliographic search (Communications of the ACM, 18(6):333–340, 1975) (PDF).

Algorithm 2 is mostly creating a trie or "keyword tree" in the paper.

Important Note: They make the assumption that $g(s, a) = \texttt{fail}$ if either $a$ is undefined, or $g(s, a)$ hasn't been defined yet. You can think of this function as an edge, it either points to the next state or returns $\texttt{fail}$. Assume evaluating and assigning to functions, such as $g$ or $output$, takes constant time.

Example:

Let's consider the intuition for a single keyword $x$. Use the last graph on page 335 with his, hers and she. Let's add "hello" and verify that it takes linear time in the length. We can generalize from there.

For this example, let $y = \text{hello}$.

$s = 0$, the initial state. First, we find out that $g(0, \text{h}) = 1$ so we set $s = 1$. Next we check $g(1, \text{e})$, which takes us to $s = 2$.

Now $g(2, \textit{l}) = \texttt{fail}$, there is no edge for $\textit{l}$, we have to create a state, $s = 10$ and set $g(2, \textit{l}) = 10$. State $10$ corresponds to the string $\text{hel}$.

Again $g(10, \textit{l}) = \texttt{fail}$, we create a new state $s = 11 \text{(hell)}$. The same happens for $\textit{o}$ : $g(11, \textit{o}) = \texttt{fail}$, make a new state $12 \text{(hello)}$.

We've finished $\text{hello}$, as a last step we set $output(12) = \text{hello}$.

Rough Analysis:

Calling $g(s,a)$, assigning values, and creating new states are constant time. Since we perform a constant number of each operation per letter, the complexity is $\mathcal{O}(|\text{y}|)$.

Algorithm 2 does this for each key word. Notice that the same bound holds for each keyword added, regardless of what $g(s,a)$ returns for each letter. Then the total time complexity is $\mathcal{O}(\displaystyle \sum_i^k{|y_i|})$, proportional to the sum of the length of the keywords.

The algorithm also sets a self-loop for any unused symbols, or $g(0, a) = 0$ for all $a$ that weren't the first letter of a keyword. We only need to consider letters in the set of keywords, so this step is still bounded by the sum length.