java - 在 Java 中查找最长的正则表达式匹配？

Question

我有这个:

import java.util.regex.*;

String regex = "(?<m1>(hello|universe))|(?<m2>(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);
}

上面只打印hello而我希望它打印 hello world .

解决此问题的一种方法是重新排序 String regex = "(?<m2>(hello world))|(?<m1>(hello|universe))" 中的组但我无法控制我遇到的正则表达式......

那么找到最长匹配项的最佳方法是什么？一个明显的方法是检查 s 的所有可能子串。如此处所述(Efficiently finding all overlapping matches for a regular expression)按长度选择第一个，但即O(n^2) .我们可以做得更好吗？

Answer 1

这是一种使用匹配器区域的方法，但在字符串索引上有一个循环:

public static String findLongestMatch(String regex, String s) {
    Pattern pattern = Pattern.compile("(" + regex + ")$");
    Matcher matcher = pattern.matcher(s);
    String longest = null;
    int longestLength = -1;
    for (int i = s.length(); i > longestLength; i--) {
        matcher.region(0, i);
        if (matcher.find() && longestLength < matcher.end() - matcher.start()) {
            longest = matcher.group();
            longestLength = longest.length();
        }
    }
    return longest;
}

我强制模式匹配直到区域的末尾，然后我将区域的末尾从最右边的字符串索引向左移动。对于每个尝试过的区域结尾，Java 将匹配在该区域结尾处结束的最左边的起始子字符串，即在该位置结束的最长子字符串。最后，这只是跟踪迄今为止找到的最长匹配项的问题。

作为优化问题，由于我是从较长的区域开始向较短的区域开始的，所以我会在之后的所有区域都已经短于已找到的最长子字符串的长度时立即停止循环。

---

这种方法的一个优点是它可以处理任意正则表达式并且不需要特定的模式结构:

findLongestMatch("(?<m1>(hello|universe))|(?<m2>(hello world))", "hello world")
==> "hello world"

findLongestMatch("hello( universe)?", "hello world")
==> "hello"

findLongestMatch("hello( world)?", "hello world")
==> "hello world"

findLongestMatch("\\w+|\\d+", "12345 abc")
==> "12345"