VAC Secured
You are an engineer on Valve's VAC (Valve Anti-Cheat) team. VAC works by scanning game memory dumps for known cheat signatures. Each cheat has a unique byte signature represented as a string pattern. When a memory dump arrives, you must find ALL occurrences of ANY known cheat signature simultaneously — running a separate scan per signature is too slow at scale.
Given a memory dump text and a list of cheat signature patterns, return all matches as a sorted list of [start_index, pattern_index] pairs, where start_index is the 0-based position in the text and pattern_index is the 0-based index in the patterns list. Sort by start_index, then by pattern_index for ties.
Your solution must scan the text only once — running KMP separately per pattern is O(n×k) and will time out.
Example 1
("superman", ["superman", "man"])[[0, 0], [5, 1]]superman matches at 0. man is a suffix of superman — the Aho-Corasick output link correctly reports both matches when the trie reaches the end of superman.
Example 2
("program", ["pro", "program"])[[0, 0], [0, 1]]Both pro (prefix) and program match starting at position 0. The trie correctly reports the shorter pattern as it passes through that node.
Example 3
("aaaaa", ["aa"])[[0, 0], [1, 0], [2, 0], [3, 0]]Overlapping matches — aa matches at positions 0, 1, 2, 3. Aho-Corasick uses failure links to find overlapping occurrences without resetting.
- ›1 <= len(text) <= 10^5
- ›1 <= len(patterns) <= 100
- ›1 <= len(patterns[i]) <= 100
- ›All strings contain only lowercase English letters
Loading question…