尝试在java中使用regex时堆栈溢出

Question

我读了一些关于如何优化正则表达式的文章，但是没有一个答案（更少的组，使用{X，Y}而不是*）似乎阻止了我的正则表达式获得堆栈溢出错误。

我正在尝试通过文件进行动态搜索。假设我正在一个相当大（2-4MB）的文件中搜索“我打赌你找不到我”。我的正则表达式生成器将生成正则表达式：

i(?:.|\s)*?bet(?:.|\s)*?you(?:.|\s)*?cannot(?:.|\s)*?find(?:.|\s)*?me

这个正则表达式的想法是，无论单词之间有什么字符或空格，它都能找到准确的短语。然而，当我尝试使用：

Pattern p = Pattern.compile(generatedRegex, Pattern.MULTILINE);
Matcher m = p.matcher(fileContentsAsString);
while (m.find()) {
System.out.println(m.group())
}

我遇到堆栈溢出错误。我知道正则表达式使用递归，但它似乎并没有正则表达式那么糟糕。有没有办法优化这个正则表达式？谢谢

回答：

Pattern p = Pattern.compile("i(?:.*)bet(?:.*)you(?:.*)cannot(?:.*)find(?:.*?)me", Pattern.DOTALL);

是我最终使用的模式/正则表达式。看起来很快，不再出现堆栈溢出异常

Answer 1

我认为你得到了很多回溯，因为你不情愿的限定符（*？）.防止回溯的一种方法是使用原子分组（？

根据评论，你也更喜欢只捕捉离“下注”最近的“i”，以减少整体匹配的长度。因为你想得到最接近其余单词的“i”，那么在我为单词2添加了否定性前瞻的地方，你也应该为单词1添加一个否定性前瞻，就在它旁边。换句话说，（？！打赌）会变成（？！i）（？！打赌）或（？！i|bet）.我已经编辑了下面的代码来包含这个需求。

String fileContentsAsString = "ii ... bet ... you, ibetyouyou";
String regex = "i(?>(?!i|bet).)*+bet(?>(?!you).)*+you";
Pattern p = Pattern.compile(regex, Pattern.DOTALL);
Matcher m = p.matcher(fileContentsAsString);
while (m.find()) {
    System.out.println(m.group());
}

输出：

我打赌你

ibetyou

解释（来源）：

“不情愿的量词的工作方式是，每次它应该尝试匹配时，它首先尝试让正则表达式的下一部分匹配。因此，它实际上是在每次迭代的开始进行前瞻，这可能会变得非常昂贵，尤其是当量化的部分每次迭代只匹配一个字符时，比如。*？"