Answer

SOLUTION

The bug: the build step records each node's own pattern list (_outputs[node]) but nothing links a node to the pattern-owning nodes on its failure chain, so scanning only reports the longest signature ending at a position. The fix is output-link propagation: during the BFS that computes failure links, also record for every node the nearest pattern-owning node on its failure chain; at scan time, walk that chain and report every pattern found.

Files: /workspace/aho_corasick.py (fix), /workspace/test_aho_corasick.py (19 regression tests).

The fix (aho_corasick.py) — build step:

while queue:
    v = queue.popleft()
    # THE FIX: output-link propagation.
    # fail[v] is the longest proper suffix of v's string; if it owns a
    # pattern, it is v's output link, else reuse fail[v]'s own output link
    # (already computed: BFS visits shallower nodes first).
    f = self._fail[v]
    self._output_link[v] = f if self._outputs[f] else self._output_link[f]
    for ch, u in self._goto[v].items():
        f = self._fail[v]
        while f and ch not in self._goto[f]:
            f = self._fail[f]
        self._fail[u] = self._goto[f].get(ch, 0)
        queue.append(u)

Scan step — report every pattern ending at the position, not just the node's own:

def scan(self, text):
    node = 0
    for pos, ch in enumerate(text):
        while node and ch not in self._goto[node]:
            node = self._fail[node]
        node = self._goto[node].get(ch, 0)
        v = node
        while v != -1:                      # own outputs + output-link chain
            for idx in self._outputs[v]:
                yield pos, idx
            v = self._output_link[v]

This is the lazy, copy-free equivalent of eagerly copying each failure-chain descendant's output set into every node: no pattern lists are duplicated, scan adds only O(matches) work, and every suffix that is a signature is reported.

>>> ac = AhoCorasick(["she", "he"])
>>> list(ac.scan("she"))          # was: only [(2, 0)] ("she")
[(2, 0), (2, 1)]                  # now: "she" and "he" both ending at index 2

EVIDENCE

Verified by running python3 -m unittest test_aho_corasick -v → 19 tests, all pass (0.011s). The suite includes a randomized differential test (300 trials, random patterns/text over {a,b}/{a,b,c}, comparing against a brute-force matcher) plus targeted regressions:

• Exact reported bug — test_nested_suffix_she_he: ["she","he"] on "she" reports both at index 2; test_only_longest_would_be_reported_without_fix guards that the "he" match is present.
• Nested/deep failure chains — ["a","ba","cba","dcba"] on "xxdcba" reports all 4 at position 5 (multi-level output-link traversal).
• Classic reference — ["he","she","his","hers"] on "ushers" → she,he @3 and hers @5.
• Overlapping signatures — ["ab","bcd"] on "abcd"; ["ab","bc","abc"] on "abc" (also verifies a prefix of a signature is not wrongly reported as a suffix); ["a","aa","aaa"] on "aaaa" → 9 matches; three patterns ending at one position.
• Edge cases — empty text, no matches, single-char patterns, duplicate signatures, empty pattern (matches at every position), unicode ("你","你好","好"), and bytes payloads (b"she" — packet-payload style, works since per-char iteration yields ints used directly as edge labels).

Notably, the four initially failing assertions were all wrong hand-written expectations on my side (e.g., "ab" is not a suffix of "abc"); the differential test against the brute-force reference passed from the start, confirming the automaton itself was correct.

SIGNATURES

{"problem_class":"python-aho-corasick-output-link-propagation","model":"deepseek-v4-flash","result":"passed","tests":19}