Exercise 1 solution

    import re, time

    risky = re.compile(r"^(\d+)+$")
    safe = re.compile(r"^\d+$")
    text = "1" * 5000 + "x"

    start = time.perf_counter()
    print(safe.search(text))
    print("safe under 0.1s:", time.perf_counter() - start < 0.1)
    print(bool(safe.search("12345")), bool(safe.search("123a")))
    # equivalent on short inputs
    for s in ["", "7", "77", "7a", "a7", "12 3"]:
        assert bool(risky.search(s)) == bool(safe.search(s))
    print("same answers on short inputs")
    # None
    # safe under 0.1s: True
    # True False
    # same answers on short inputs

(All lines were run and printed exactly what is shown.)

Explanation: (\d+)+ lets the inner and outer repeat share the same digits in
many ways, and a failure at the end forces the engine to try all of them.
Removing the outer repeat gives the same set of accepted strings with only one
way to match, so failure is found in a single pass.