Negative Regexp

Question

Write the shortest function that takes one string, and returns a regular expression that matches anything EXCEPT the input string, in parenthesis. Escape necessary characters like Perl quotemeta.

Input:
  helloworld
Output:
  ([^h]|h[^e]|he[^l]|hel[^l]|hell[^o]|hello[^w]|hellow[^o]|hellowo[^r]|hellowor[^l]|helloworl[^d])
Input:
  */
Output:
  ([^\*]|\*[^\/])

See also:

• http://yannesposito.com/Scratch/en/blog/2010-02-15-All-but-something-regexp/
• http://shinkirou.org/blog/2010/12/tricky-regular-expression-problems/

Answer 1

Python, 49 chars

import re
f=lambda x:'(^(?!%s$).*$)'%re.escape(x)

The answer matches anything but the input. It gives an output using conditional groups so is suited for the problem:

regular expression that matches anything EXCEPT the input string

The answer uses Howard's regex (fixing my regex)

You can use the same approach on Perl with a few less chars:

Perl, 40 38

sub f{'(^(?!'.quotemeta(pop).'$).*$)'}

Examples:

f('hello') -> (^(?!hello$).*$)

f('*/')    -> (^(?!\*\/$).*$)

Answer 2

Perl, 32 bytes

sub{qr/^\Q$_[0]\E\z(*COMMIT)a|/}

Try it online!

This is actually a general-purpose negator for any regular expression that doesn't use control flow commands. The basic idea is that we do (*COMMIT) ("if this doesn't match, nothing can"), followed by something that can't possibly match (a true general-purpose negator would use (?!), but we can use just a in this context because we know it can't appear after the end of the string \z), in order to force a failure in cases where the initial regular expression matches; | then allows a success in all other cases.

Out of the 31 bytes here:

• sub{, $_[0], } (10 bytes) handle I/O (because the original question asked specifically for a function);
• qr/^\Q, \E\z, / (11 bytes) construct a regex that matches the string provided as input, and only that string (we return the regex as a regex object; a string would be 1 byte shorter, but the regex object happens to come with parentheses around it, as required by the question, and a string would require me to add parentheses manually);
• (*COMMIT)a| (11 bytes) are the regex negator that we use to negate that regex.

It's notable how much boilerplate there is here, and how the answer might be shorter if the question were more difficult (allowing the negation of arbitrary regexes, rather than just ones that match a single string).

Answer 3

JAVA 61

String f(String w){return "^(?!"+Pattern.quote(w)+"$)(.*)$";}