如何在 java 中使用正则表达式查找字符串中最后一次出现的一组字符？

Question

我需要找到字符串中字符集的最后一个索引。考虑字符集 x,y,z 和字符串 Vereador Luiz Pauly Home 然后我需要索引 18.

所以为了找到索引，我创建了一个带有 DOTALL 标志和 greedy quantifier 的模式作为 (?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;
}

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

But if there is no match, then it takes too long time (17 minutes for 600000 characters) as it is a Greedy match.

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

PS: 我也可以考虑遍历上次的内容并找到 index.But 我希望正则表达式中有一些更好的方法可以快速完成这项工作。

Answer 1

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

反转输入字符串和可能的模式，这可能适用于 non-complex 模式。不幸的是 java.util.regex 不允许从右到左匹配模式。
不是使用贪心量词，而是简单地匹配模式并循环 Matcher.find() 直到找到最后一个匹配项。
使用性能更好的不同正则表达式引擎，例如RE2/J: linear time regular expression matching in Java.

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

Java's standard regular expression package, java.util.regex, and many other widely used regular expression packages such as PCRE, Perl and Python use a backtracking implementation strategy: when a pattern presents two alternatives such as a|b, the engine will try to match subpattern a first, and if that yields no match, it will reset the input stream and try to match b instead.

If such choices are deeply nested, this strategy requires an exponential number of passes over the input data before it can detect whether the input matches. If the input is large, it is easy to construct a pattern whose running time would exceed the lifetime of the universe. This creates a security risk when accepting regular expression patterns from untrusted sources, such as users of a web application.

In contrast, the RE2 algorithm explores all matches simultaneously in a single pass over the input data by using a nondeterministic finite automaton.

Answer 2

(?s).*(x|y|z) 正则表达式的性能问题来自以下事实：.* 模式是第一个首先获取整个字符串的子模式，然后发生回溯以找到 x，y 或 z。如果没有匹配，或者匹配在字符串的开头，并且字符串非常大，这可能需要很长时间。

([xyz])(?=[^xyz]*$) 模式似乎好一点：它捕获 x、y 或 z 并断言没有其他 x、y 或 z 直到字符串的末尾，但它也有点 resource-consuming 由于找到匹配后的每个前瞻检查。

完成工作最快的正则表达式是

^(?:[^xyz]*+([xyz]))+

匹配

^ - 字符串开头
(?:[^xyz]*+([xyz]))+ - 重复 1 次或多次
- [^xyz]*+ - 除了 x、y 和 z 以外的任何 0 个或更多字符都进行了所有格匹配（不允许回溯到模式中）
- ([xyz]) - 第 1 组：x、y 或 z.

第 1 组的值和数据将属于重复组的最后一次迭代（因为所有前面的数据都是 re-written 每次后续迭代）。

Answer 3

StringBuilder 都有一个 reverse 并且是一个 CharSequence，因此可以进行搜索。

Pattern p = Pattern.compile("[xyz]");
StringBuilder sb = new StringBuilder(str).reverse();
Matcher m = p.matcher(sb);
return m.find() ? sb.length() - m.end() : -1;

不幸的是，逆转代价高昂。

没有正则表达式的解决方案可能更快。

（BTW 代理对已通过反转正确处理。）

如何在 java 中使用正则表达式查找字符串中最后一次出现的一组字符？

How to find a last occurrence of set of characters in string using regex in java?

java

regex

regex-greedy