Construction of Aho Corasick automaton in linear time for integer alphabets

We present a new simple algorithm that constructs an Aho Corasick automaton for a set of patterns, P, of total length n, in O(n) time and space for integer alphabets. Processing a text of size m over an alphabet Σ with the automaton costs O(mlog|Σ|+k), where there are k occurrences of patterns in the text.A new, efficient implementation of nodes in the Aho Corasick automaton is introduced, which works for suffix trees as well.