= Alfred V. Aho
{c}
<Alfred V. Aho> coauthored <Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick> with <Margaret J. Corasick> in 1975. Their <Aho-Corasick algorithm> constructs a machine for a whole <string>[pattern] dictionary and searches a <string>[text] in a single pass.<Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick>[abstract]{ref}
Its useful distinction is between <string>[text] progress and <string>[pattern] progress. On a failed extension, a <failure link> changes the candidate <string>[pattern] <string prefix>[prefix] without moving backward in the <string>[text]. Shared <string prefix>[prefixes] and <string suffix>[suffix] continuations avoid repeating a complete independent search for every keyword, while reporting cost still grows with the number of actual matches.
Back to article page
