Avoid overlapping regex matching in Java

Question

For some reason this piece of Java code is giving me overlapping matches:

Pattern pat = Pattern.compile("(" + leftContext + ")" + ".*" + "(" + rightContext + ")", Pattern.DOTALL);

any way/option so it avoids detecting overlaps? e.g. leftContext rightContext rightContext should be be 1 match instead of 2

Here's the complete code:

public static String replaceWithContext(String input, String leftContext, String rightContext, String newString){   
  Pattern pat = Pattern.compile("(" + leftContext + ")" + ".*" + "(" + rightContext + ")", Pattern.DOTALL);
  Matcher matcher = pat.matcher(input);
  StringBuffer buffer = new StringBuffer();

  while (matcher.find()) { 
   matcher.appendReplacement(buffer, "");
   buffer.append(matcher.group(1) + newString + matcher.group(2));
  }
  matcher.appendTail(buffer);

  return buffer.toString();
 }

So here's the final answer using a negative lookahead, my bad for not realizing * was greedy:

Pattern pat = Pattern.compile("(" +
    leftContext + ")" + "(?:(?!" +
    rightContext + ").)*" + "(" +
    rightContext + ")", Pattern.DOTALL);

Can you tell us what leftContext and rightContext are? And give us an example of a failing match. — moinudin
– moinudin, Commented Nov 27, 2010 at 9:05
Getting the regex matcher to capture overlapping things is usually a slightly tricky matter, not something that happens by default. Without seeing the contents of the patterns, it's hard to say what is happening. It would basically require lookarounds to get the matcher to go over the same part of the string more than once. Are you doing that? — tchrist
– tchrist, Commented Nov 27, 2010 at 13:52
rightContext and leftContext are plain Strings e.g leftContext="ab" rightContext="cd" — Ricardo
– Ricardo, Commented Nov 29, 2010 at 5:12
The * quantifier is greedy by default, the regex you describe would not produce multiple matches. Why don't you post a complete example? — Dmitri
– Dmitri, Commented Nov 29, 2010 at 5:25
ah, so thats what happening, any chance i can change the default behavior of * to be non-greedy? — Ricardo
– Ricardo, Commented Nov 29, 2010 at 8:24

Alan Moore · Accepted Answer · 2010-11-29 21:40:44Z

Your use of the word "overlapping" is confusing. Apparently, what you meant was that the regex is too greedy, matching everything from the first leftContext to the last rightContext. It seems you figured that out already--and came up with a better approach as well--but there's still at least one potential problem.

You said leftContext and rightContext are "plain Strings", by which I assume you meant they aren't supposed to be interpreted as regexes, but they will be. You need to escape them, or any regex metacharacters they contain will cause incorrect results or run-time exceptions. The same goes for your replacement string, although only $ and the backslash have special meanings there. Here's an example (notice the non-greedy .*?, too):

public static String replaceWithContext(String input, String leftContext, String rightContext, String newString){
  String lcRegex = Pattern.quote(leftContext);
  String rcRegex = Pattern.quote(rightContext);
  String replace = Matcher.quoteReplacment(newString);
  Pattern pat = Pattern.compile("(" + lcRegex + ").*?(" + rcRegex + ")", Pattern.DOTALL);

One other thing: if you aren't doing any post-match processing on the matched text, you can use replaceAll instead of rolling your own with appendReplacement and appendTail:

return input.replaceAll("(?s)(" + lcRegex + ")" +
                        "(?:(?!" + rcRegex + ").)*" +
                        "(" + rcRegex + ")",
    "$1" + replace + "$2");

darioo · Accepted Answer · 2010-11-27 08:57:41Z

1

There are few possibilities, depending on what you really need.

You can append $ at the end of your regex, like this:

"(" + leftContext + ")" + ".*" + "(" + rightContext + ")$"

so if rightContext isn't the last thing, your regex won't match.

Next, you can capture everything after rightContext:

"(" + leftContext + ")" + ".*" + "(" + rightContext + ")(.*)"

and after that discard everything in your third matching group.

But, since we don't know what leftContext and rightContext really are, maybe your problem lies within them.

answered Nov 27, 2010 at 8:57

darioo

47.4k10 gold badges79 silver badges104 bronze badges

1 Comment

Ricardo Over a year ago

mm, not sure how that will work in my code, i cannot just discard parts of the input string

Collectives™ on Stack Overflow

Avoid overlapping regex matching in Java

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related