如何在Java中使用正则表达式查找字符串中最后一组字符？

Question

我需要找到字符串中字符集的最后一个索引。考虑字符集为x，y，z和string作为Vereador Luiz Pauly Home，那么我需要index为18。

因此，寻找索引我已经创建了一个模式DOTALL标志和贪婪量词为*（S？）。（X | Y | Z） 。当模式应用于该字符串（多行）时，我可以从起始组中找到索引。代码：

int findIndex(String str){
  int index = -1;
  Pattern p = Pattern.compile("(?s).*(x|y|z)");
  Matcher m = regex.matcher(str);
  if(m.find()){
    index = m.start(1);
  }
  return index;
}

如预期的那样，如果匹配，它将正确返回值。

但是，如果没有匹配项，则它花费的时间太长（600000个字符需要17分钟），因为它是贪婪的匹配项。

我尝试了其他量词，但无法获得所需的输出。那么，谁能推荐更好的正则表达式呢？

PS：我也可以考虑从最后遍历内容并找到索引。但是我希望正则表达式中有更好的方法可以快速完成工作。

Answer 1

解决该问题的方法很少，最好的方法取决于输入的大小和模式的复杂性：

1. 反转输入字符串和可能的模式，这可能适用于非复杂模式。不幸的java.util.regex是不允许从右到左匹配模式。

2. 不使用贪婪量词，只需匹配模式并循环，Matcher.find()直到找到最后一个匹配项。

3. 使用具有更好性能的不同正则表达式引擎，例如RE2/J：Java 中的线性时间正则表达式匹配。

如果选项 2 对于您的情况来说不够有效，我建议尝试 RE2/J：

Java 的标准正则表达式包 java.util.regex 以及许多其他广泛使用的正则表达式包（例如 PCRE、Perl 和 Python）都使用回溯实现策略：当一个模式出现两个替代方案（例如 ）时，a|b引擎将a首先尝试匹配子模式，如果没有匹配，它将重置输入流并尝试匹配b。

如果此类选择是深度嵌套的，则该策略需要对输入数据进行指数次数的传递，然后才能检测输入是否匹配。如果输入很大，很容易构建一个运行时间超过宇宙寿命的模式。当接受来自不可信来源（例如 Web 应用程序的用户）的正则表达式模式时，这会产生安全风险。

相比之下，RE2 算法使用非确定性有限自动机在一次输入数据中同时探索所有匹配项。