Regex for `x...(a and b)...y` within a limited length?

user_1667884 0
Viewed 196

Is it possible to specify a regex that matches x...(a and b)...y within a limited length of n?

To be more precise:

  1. The length of chars between the matched x and y must be at most n.
  2. Both an a and a b (regardless of order) must exist between the matched x and y.
  3. x, a, b, and y here could stand for a multi-char string snippet.

Test cases (assume n = 10):

Match:
...x..a...b..y...
...x..b...a..y...
...x..a...b..y...a...
...x..a...b..y...b...
...x..a...b..y...y...
...x..a.x.b..y...
...x..a.y.b..y...
...xaabbaabbay...
...x..a...b..y... ...x..a...b..y... (2 matches)
...xaby...xaby... (2 matches)

Don't match:
...x..a...b......
...x......b..y...
...x..a......y...
...x..a...b......y...
...x......b..y...a...
...x..a......y...b...
...x..a.y.b......
...x..a.y.b......y...
...x..a.y.b.x....y...
.a.x......b..y...
.b.x..a......y...

P.S: I know that this can be done by simply match /x.{0,n}y/ and then check whether a and b both exist in the matched string in many programming languages. However, this question explicitly requests for a single regex approach, so that it can be used as a query in some applications, such as Google Doc and Notepad++.

notepad++ regex
2 Answers

I believe you can use

x(?:(?(1)(?!)|(a))|(?(2)(?!)|(b))|.){0,10}?y(?(1)|(?!))(?(2)|(?!))

See the regex demo. Details:

  • x - left-hand delimiter
  • (?:(?(1)(?!)|(a))|(?(2)(?!)|(b))|.){0,10}? - zero to ten occurrences (but as few as possible) of
    • (?(1)(?!)|(a)) - if Group 1 is null (if Group 1 was not matched before) match a, else, fail to trigger backtracking right away
    • | - or
    • (?(2)(?!)|(b)) - if Group 2 is null (if Group 2 was not matched before) match b, else, fail to trigger backtracking right away
    • |. - or any one char (other than line break char by default)
  • y - right-hand delimiter
  • (?(1)|(?!)) - conditional construct: if Group 1 participated in the match (if Group 1 value is not null), proceed, else, fail the match
  • (?(2)|(?!)) - conditional construct: if Group 2 participated in the match (if Group 2 value is not null), proceed, else, fail the match.

The last two conditionals make sure there is a and b in the matched text.

NOTE: If a and b can be multicharacter strings, n must be reduced to the length that is n-(a.length-b.length+2). So, if a is ac and b is bmc, you need to replace 10 with 10-(2-3+2) => 7. This also means you should check your expected limit length restriction beforehand, it should allow the length of both a and b combined.

NOTE 2: Add (?s) at the beginning of the pattern to match line break chars with . as well. See How do I match any character across multiple lines in a regular expression? for more options.

user_38329700

I fear this is not possible without generating all valid combinations of lengths for the parts between x and a|b, between a and b, and between a|b and y.

For n=5 (i.e. 0-3 characters other than the a and b between x and y:

x ( [^ab]{0} ( a ( [^b]{0} b .{0,3}
                 | [^b]{1} b .{0,2}
                 | [^b]{2} b .{0,1}
                 | [^b]{3} b .{0}   )
             | b ( [^b]{0} a .{0,3}
                 | [^b]{1} a .{0,2}
                 | [^b]{2} a .{0,1}
                 | [^b]{3} a .{0}   ) )
  | [^ab]{1} ( a ( [^b]{0} b .{0,2}
                 | [^b]{1} b .{0,1}
                 | [^b]{2} b .{0}   )
             | b ( [^b]{0} a .{0,2}
                 | [^b]{1} a .{0,1}
                 | [^b]{2} a .{0}   ) )
  | [^ab]{2} ( a ( [^b]{0} b .{0,1}
                 | [^b]{1} b .{0}   )
             | b ( [^b]{0} a .{0,1}
                 | [^b]{1} a .{0}   ) )
  | [^ab]{3} ( a ( [^b]{0} b .{0}   )
             | b ( [^b]{0} a .{0}   ) ) ) y

I used [^…] instead of . to avoid too much backtracking from the wrong branch, though it could probably be optimised a bit further.

user_10485720
Related