# Negative Regexp [closed]

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:
([^\*]|\*[^\/])


• I would have thought that that could be done more concisely in regex. – Peter Olson Jul 11 '11 at 5:47
• The resulting regexes are somehow strange. E.g. The first one will match "x" or "hx" but not "xx". This is not "anything except the input". What do you really want to match? – Howard Jul 11 '11 at 6:12
• Or ^(?!hello$)(.*)$ should work also (depending on the exact requirement - it matches anything which is not exactly "hello", i.e. "hello!" would match). – Howard Jul 11 '11 at 7:13
• actually the regex I wrote had a problem. But I think there's a way to do that – JBernardo Jul 11 '11 at 7:18
• Your example output for 'helloword' doesn't match the string 'h' or '' – Rob Jul 20 '11 at 2:15

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('*/')    -> (^(?!\*\/$).*$)

• You can save two by replacing $_[0] with pop. – Howard Jul 11 '11 at 7:48 • @Howard that's right. But as the question asks for parenthesis in the answer, I added 2 chars too :) – JBernardo Jul 11 '11 at 7:54 • You only need the parenthesis only once, either around the statement or around .*. – Howard Jul 11 '11 at 8:03 # 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). JAVA 61 String f(String w){return "^(?!"+Pattern.quote(w)+"$)(.*)$";}  • String f(String w){return "^(?!\\Q"+w+"\\E)(.*)$";} – Prince John Wesley Jul 21 '11 at 10:34
• @john that doesn't escape \E in the input string – ratchet freak Jul 21 '11 at 11:54
• yes. make sense.+1 – Prince John Wesley Jul 21 '11 at 11:56