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.
Why does the construction step of Aho-Corasick take linear time in the number of nodes?
ds.algorithms;ds.data structures;time complexity;string matching