Aho–Corasick algorithm

Construction inserts a finite set of nonempty keywords into a trie, sharing prefix paths and recording terminal outputs. The resulting machine scans text without independently rereading it for every pattern.

For he, she, his and hers, processing ushers reaches a state that reports both she and its suffix he. One state can therefore have multiple outputs; reporting merely “some word matched” loses valid occurrences.

References: [1]

If no transition exists for the next character, failure links retreat while retaining that same input character. Their destination represents the longest proper suffix that remains a prefix of a keyword, avoiding text backtracking.

Breadth-first construction makes shorter-state information available first and propagates suffix outputs. A fully completed deterministic transition table can replace failures with direct moves at the cost of additional entries.

References: [1]

With a fixed alphabet, constant-time transition access, identifier-based reporting, and shared outputs or output links that avoid copying every inherited set per state, construction plus search can be expressed as O(M+n+z), where M is total pattern length, n text length and z reported hits. Copying whole keywords or linear transition lookups adds costs.

The paper discusses large output sets and separate word-boundary conditions in bibliographic search. Dictionary changes require maintenance; deciding whether a common word denotes a particular entity still needs context beyond character matching.

References: [1]