Aho-Corasick — Multi-Pattern Matching

The idea

Build trie of all patterns. Add failure links (like KMP's LPS but on the trie). Walk text through the automaton.

Failure links

For each node, longest suffix that's also a prefix of some pattern. Enables jumping in O(1) on mismatch.

Complexity

O(sum of pattern lengths + text length + number of matches). Linear in inputs + outputs.

Structure

class ACNode {
  Map next = new HashMap<>();
  ACNode fail;
  List output = new ArrayList<>();
}
// Build: BFS from root. For each node, compute fail link
// Search: at each text char, follow next or fail links, collect outputs