Aho-Corasick Match Positions

Problem

Scan text once with an Aho-Corasick automaton built from patterns. Return, for each pattern in input order, the sorted list of 0-based start indices where that pattern occurs in text. Overlapping matches are all reported, and patterns may repeat. Patterns are non-empty lowercase strings.

Hint

Merge each node's match list into its failure target during BFS so one walk reports every pattern ending there.

Test cases

case 1

in: ["ababa",["aba","ba","a"]]

expected: [[0,2],[1,3],[0,2,4]]

case 2

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

expected: [[0,1,2],[0,1],[0,1,2,3]]

case 3

in: ["xyzxyz",["yz","xyz","q"]]

expected: [[1,4],[0,3],[]]

case 4

in: ["abc",["abc","ab","c"]]

expected: [[0],[0],[2]]

Starter codePython

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

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