[psurge]

I probably screwed something up, but here's a 16 line attempt in Python, where the regex specials are limited to .?:

    def matches(pattern, s):
        if len(pattern) == 0:
            return True
        c = pattern[0]
        assert c not in ("*", "?")
        if len(pattern) > 1:
            if pattern[1] == "?":
                return (
                    len(s) > 0 and c in (".", s[0]) and matches(pattern[2:], s[1:])
                ) or matches(pattern[2:], s)
            elif pattern[1] == "*":
                for i, d in enumerate(s):
                    if c not in (".", d):
                        break
                return any(matches(pattern[2:], s[j:]) for j in range(i, -1, -1))
        return len(s) > 0 and c in (".", s[0])

[m0zg]

Pretty much something along these lines, except it's also required that both pattern and s end at the same time for a full match (this complicates the base case a tiny bit). The C/C++ solution looks more elegant because you can use pointers. Note that this particular version requires no prior knowledge of the algorithm and can be solved on the spot fairly easily.

[epicureanideal]

Thanks for the demonstration!