Regular expression to match smallest only

Question

I have a expression like c.{0,2}?mand a string like "abcemtcmncefmf". Currently it will matches three substrings: cem, cm and cefm (see here). But I like to match only the smallest of this, in this case, cm.

My problem is that I don't have a global match support, only the first match, because I'm using MariaDB REGEXP_SUBSTR() function. My current solution is a stored procedure that I created to solve my problem. But it is 10 times slower than just a regular expression for simple cases.

I too tried do something like: (cm|c.{0,1}?m|c.{0,2}?m), but it doesn't worked because it will match first of any group patterns, instead of try one by one in all subject string.

I know that regular expressions (PCRE) have some black magic features, but I don't found nothing to solve my problem.

---

• Note: I'm yet using non-greedy pattern (.{0,2}?) on my current pattern;
• The question Regular expression to find smallest possible match don't is my problem;

Answer 1

There's a lot of things that regular expressions can do - some of which are - as you say - 'dark magic'. But the core problem is - pretty fundamentally, regular expressions are about text selection can capture. They don't 'do' match comparison or evaluation - they either match or they do not.

You can see what the regex is doing, by enabling it in debug mode. For this, I'll use perl because you can set use re 'debug';':

#!/usr/bin/env perl

use strict;
use warnings;

use re 'debug';

my @matches = "abcemtcmncefmf" =~ m/(cm|c.m|c..m)/;
print join "\n", @matches;

This will print what the regex engine is doing as it goes:

Compiling REx "(cm|c.m|c..m)"
Final program:
   1: OPEN1 (3)
   3:   TRIE-EXACT[c] (19)
        <cm> (19)
        <c> (9)
   9:     REG_ANY (10)
  10:     EXACT <m> (19)
        <c> (15)
  15:     REG_ANY (16)
  16:     REG_ANY (17)
  17:     EXACT <m> (19)
  19: CLOSE1 (21)
  21: END (0)
stclass AHOCORASICK-EXACT[c] minlen 1 
Matching REx "(cm|c.m|c..m)" against "abcemtcmncefmf"
Matching stclass AHOCORASICK-EXACT[c] against "abcemtcmncefmf" (14 bytes)
   0 <> <abcemtcmnc>         | Scanning for legal start char...
   2 <ab> <cemtcmncef>       | Charid:  1 CP:  63 State:    1, word=0 - legal
   3 <abc> <emtcmncefm>      | Charid:  0 CP:  65 State:    2, word=2 - fail
   3 <abc> <emtcmncefm>      | Fail transition to State:    1, word=0 - fail
Matches word #2 at position 2. Trying full pattern...
   2 <ab> <cemtcmncef>       |  1:OPEN1(3)
   2 <ab> <cemtcmncef>       |  3:TRIE-EXACT[c](19)
   2 <ab> <cemtcmncef>       |    State:    1 Accepted: N Charid:  1 CP:  63 After State:    2
   3 <abc> <emtcmncefm>      |    State:    2 Accepted: Y Charid:  0 CP:  65 After State:    0
                                  got 2 possible matches
                                  TRIE matched word #2, continuing
   3 <abc> <emtcmncefm>      |  9:  REG_ANY(10)
   4 <abce> <mtcmncefmf>     | 10:  EXACT <m>(19)
   5 <abcem> <tcmncefmf>     | 19:  CLOSE1(21)
   5 <abcem> <tcmncefmf>     | 21:  END(0)
Match successful!
Freeing REx: "(cm|c.m|c..m)"

Hopefully you can see what it's doing here?

• working from left to right
• hits the first 'c'
• checks to see if 'cm' matches (fails)
• checks to see if 'c.m' matches (succeeds).
• bails out here and returns hits.

Turn on g and you get it to work multiple times - I shan't reproduce it, but it's quite a lot longer.

Whilst you can do a lot of clever tricks with PCRE, such as look around, look ahead, greedy/nongreedy matching.... pretty fundamentally, here, you are trying to select multiple valid matches, and pick the shortest. And regex can't do that.

I would offer though - with that same perl, the process of finding the shortest is quite easy:

use List::Util qw/reduce/;
print  reduce { length( $a ) < length( $b ) ? $a : $b } @matches;

Answer 2

You can simply use an alternation in a branch reset group:

/^(?|.*(cm)|.*(c.m)|.*(c..m))/s

(The result is in group 1)

or like this:

/^.*\Kcm|^.*\Kc.m|^.*\Kc..m/s

The first successful branch wins.

Answer 3

Technically, it can be done.

my ($match) = /
   ^
   (?:(?! c[^m]{0,2}m ).)*+         # Skip past area with no matches.
   (?:
      (?:(?! c[^m]{0,1}m ).)*+      # Skip past area with no matches except longuest.
      (?:
         (?:(?! c[^m]{0,0}m ).)*+   # Skip past area with no matches except 2 longuest.
      )?
   )?
   ( c[^m]{0,2}m )
/xs;

[Note: Removing the possessive quantifier modifiers (+) will greatly affect performance.]

But it's usually far, far better to find all matches and locate the smallest one.

use List::Util qw( reduce );
my ($match) = reduce { length($a) <= length($b) ? $a : $b } /c[^m]{0,2}m/g;