Aho-Corasick Failure Link Count

Problem

Build an Aho-Corasick automaton from patterns. Each trie node's failure link points to the longest proper suffix of its path that is also a trie prefix, or the root when none exists. Return [total_nodes, non_root_failures] where total_nodes includes the root and non_root_failures counts nodes whose failure link is not the root.

Hint

Process nodes in BFS order so every failure target is already computed; follow failure links to fall back on a mismatch.

Test cases

case 1

in: [["a","aa"]]

expected: [3,1]

case 2

in: [["ab","bc"]]

expected: [5,1]

case 3

in: [["aaa"]]

expected: [4,2]

case 4

in: [["he","she"]]

expected: [6,2]

case 5

in: [["a","ab"]]

expected: [3,0]

Starter codePython

def ac_failure_links(patterns):
    # Your code here
    pass

5 test cases · run your code against them in the editor