Match longest string in Regex OR in case of common substring

Question

In a regex OR, When there are multiple inputs with a common prefix, The regex will match the first input in Regex OR instead of longest match.

For example, for the regular expression regex = (KA|KARNATAKA) and input = KARNATAKA the output will be 2 matches match1 =KA and match2 = KA.

But what I want is complete longest possible match out of given input in Regex OR which is match1 = KARNATAKA in my given example.

Here is the example in a regex client

So what I am doing right now is, I am sorting the input in Regex OR by length in descending order.

My question is, Can we specify in the regex itself to match the longest possible String? Or is sorting the only way to do it?

I have already refered this question and I don't see a solution other than sorting

@SHAHAKASH What if he wants to match `KARNA`. Your solution `\b(KA|KARNA)\b` won't work there — Gurmanjot Singh, Feb 21 '19 at 05:51
@Jai there's no problem sorting the inputs when the input is very less or it's a one time job. There will be a performance issue when we've huge input and we've to do it again and again dynamically. I just wanted to know if we can let the `Regex engine ` handle this. — Arun Gowda, Feb 21 '19 at 06:04
Why not use regex quantifiers _*_ like [this](https://regex101.com/r/ecpo5R/2) ? — Rahul, Feb 21 '19 at 06:14
@Rahul Because he does not want to match [`KABLABLABLA`](https://regex101.com/r/ecpo5R/3) — Gurmanjot Singh, Feb 21 '19 at 06:16
@Rahul what if someone enters KAAAA? your solution won't work — Akash Shah, Feb 21 '19 at 06:16
https://stackoverflow.com/questions/35997376/how-to-order-regular-expression-alternatives-to-get-longest-match/36296918 — Akash Shah, Feb 21 '19 at 06:31
try to use word boundary `\b`, `(\bKA\b|\bKARNATAKA\b)` will work — The Scientific Method, Feb 21 '19 at 06:41

score 1 · Answer 1 · answered Feb 21 '19 at 06:57

1

You can use word boundary (\b) to avoid matching prefixes

For the case you mentioned: the following regex will only match KA or KARNATAKA

(\bKA\b|\bKARNATAKA\b)

Try here

answered Feb 21 '19 at 06:57

The Scientific Method

2,374
2
14
25

What if he wants to match KARNA. Your solution (\bKA\b|\bKARNATAKA\b) won't work there see in a comment. – Akash Shah Feb 21 '19 at 07:07
1

@SHAHAKASH It is *not* supposed to match "KARNA". – Jai Feb 21 '19 at 07:08
he wants longest match. – Akash Shah Feb 21 '19 at 07:08
@SHAHAKASH Longest *exact* match. – Jai Feb 21 '19 at 07:09
if String test="KA KARN" --> then he wants KARN, not KA that's a question if I not wrong. – Akash Shah Feb 21 '19 at 07:15

score 0 · Answer 2 · answered Feb 21 '19 at 07:05

You can create a helper method for this:

public final class PatternHelper {
    public static Pattern compileSortedOr(String regex) {
        Matcher matcher = Pattern.compile("(.*)\\((.*\\|.*)\\)(.*)").matcher(regex);

        if (matcher.matches()) {
            List<String> conditions = Arrays.asList(matcher.group(2).split("\\|"));
            List<String> sortedConditions = conditions.stream()
                                                      .sorted((c1, c2) -> c2.length() - c1.length())
                                                      .collect(Collectors.toList());

            return Pattern.compile(matcher.group(1) +
                                       "(" +
                                       String.join("|", sortedConditions) +
                                       ")" +
                                       matcher.group(3));
        }

        return Pattern.compile(regex);
    }
}

Matcher matcher = PatternHelper.compileSortedOr("(KA|KARNATAKA)").matcher("KARNATAKA");
if (matcher.matches()) {
    System.out.println(matcher.group(1));
}

Output:

KARNATAKA

P.S. This only works for simple expressions without nested brackets. You would need to tweak if you are expecting much complex expressions.

Match longest string in Regex OR in case of common substring

2 Answers2