NFA simulation
Simulate active states in parallel and process long ambiguous inputs within the execution deadline.
Build it in your language
The tester treats your program as a black box: any language works. These are just the most convenient ones for this project.
NFA simulation without exponential backtracking
Your parser already recognizes patterns. Convert that structure into an automaton with character and empty (epsilon) transitions. nfa-match must consume the complete text; earlier search behavior remains unchanged.
Observable contract
Input: {"op":"nfa-match","pattern":"(a|aa)*b","text":"aaaab"}. Output: {"matched":true} followed by a newline. This operation returns neither captures nor a self-declared step counter. Dot excludes \n.
Maintain a set of active states. Expand its epsilon closure without visiting a state twice in one expansion. For each character compute the next set and expand again. Accept only if the final state is active after all text is consumed.
Complexity and verification
Tests include 4,096 letters a followed by b or c with (a|aa)*b. The process must finish within the contract's 2,000 ms, including startup: compile before running. This detects naive exponential backtracking; it does not alone prove an asymptotic bound. Also explain why each step processes at most the automaton's states, yielding O(text length × states).
Do not delegate to the language's regex engine. Use sets and stable state IDs. Check empty text, epsilon cycles, and patterns leaving trailing text. Invalid JSON, missing fields, or invalid patterns produce error on stderr, empty stdout, and exit 1; valid inputs exit 0.
Output and errors
Multiline examples are formatted for readability. Emit compact JSON without optional spaces, with properties in the order shown by the output examples, and a final newline. Keep logs off stdout. Tests compare exact text.
Invalid inputs use stderr containing error, empty stdout, and exit 1. Valid inputs exit 0. Serialize integer results as JSON integers.