Build your own regex engine
Stage 2 of 8v2 · d2c34479

Anchors and search

Distinguish matching from the start versus searching any position, and apply ^ and $.

Build it in your language

TypeScriptPythonRust

The tester treats your program as a black box: any language works. These are just the most convenient ones for this project.

Anchors (^ and $) and Substring Search

Unlike prefix matching, search looks for pattern occurrences across arbitrary offsets unless constrained by anchors:

  • ^: Anchors matching to text start (offset 0).
  • $: Anchors matching to text end.

Mental Model: Sliding Offset and Anchors

  • If prefixed with ^: only evaluate at index 0.
  • Otherwise: slide starting index ii across text length.
  • If suffixed with $: ensure matching consumes text until end.

Your Goal in this Stage

Implement op: "search" with ^ and $ anchor support.

Input Format

json
{
  "op": "search",
  "pattern": "^cat$",
  "text": "a cat"
}

Output Format

json
{
  "matched": false
}

Step-by-Step Implementation Guide

  1. Parse anchors: Extract leading ^ and trailing $.
  2. Scan offsets: Test match starting at each position.
  3. Enforce $: Ensure candidate match reaches string end.
  4. Emit output: Print JSON object.

Acceptance Criteria

  • ✅ Correctly enforces ^ and $.
  • ✅ Discovers substring matches anywhere in text when unanchored.

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.