title: Finding longest regex match in Java?
body: <p>I have this:</p>
  
  <pre><code>import java.util.regex.*;
  
  String regex = "(?&lt;m1&gt;(hello|universe))|(?&lt;m2&gt;(hello world))";
  String s = "hello world";
  
  Pattern pattern = Pattern.compile(regex);
  Matcher matcher = pattern.matcher(s);
  while(matcher.find()) {
    MatchResult matchResult = m.toMatchResult();
    String substring = s.substring(matchResult.start(), matchResult.end());
    System.out.println(substring);
  }
  </code></pre>
  
  <p>The above only prints <code>hello</code> whereas I want it to print <code>hello world</code>. </p>
  
  <p>One way to fix this is to re-order the groups in <code>String regex = "(?&lt;m2&gt;(hello world))|(?&lt;m1&gt;(hello|universe))"</code> but I don't have control over the regex I get in my case...</p>
  
  <p>So what is the best way to find the longest match? An obvious way would be to check all possible substrings of <code>s</code> as mentioned here (<a href="https://stackoverflow.com/questions/11371365/efficiently-finding-all-overlapping-matches-for-a-regular-expression?noredirect=1&amp;lq=1">Efficiently finding all overlapping matches for a regular expression</a>) by length and pick the first but that is <code>O(n^2)</code>. Can we do better?</p>