Aho-Corasick Matches

Problem

Given text and a list of patterns, return the total number of pattern occurrences in text, counting overlapping matches and repeated patterns separately.

Build a trie with failure links and accumulated output counts, then run the automaton over the text. Return 0 for no matches, and an empty pattern list gives 0.

Hint

Output counts propagate along failure links so suffix patterns are also counted.

Test cases

case 1

in: ["ahishers",["he","she","his","hers"]]

expected: 4

case 2

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

expected: 7

case 3

in: ["abc",["d"]]

expected: 0

case 4

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

expected: 0

case 5

in: ["abab",["ab","ba"]]

expected: 3

Starter codePython

def aho_corasick_matches(text, patterns):
    # Your code here
    pass

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