Java 需要过长的时间来确定字符串是否与 String.matches 匹配

Question

我有以下正则表达式，它匹配开头以括号中的文本结尾的任何字符“Hi (Stackoverflow)”。

当我输入要匹配的文本时，程序就会继续运行。

String pattern = "^[a-zA-Z]+([\\s]*[\\w]*)*\\([\\w]+\\)"
String text = "Asdadasdasd sadsdsad sdasd (s)"
String text2 = "Asdadasdasd sadsdsad sdasd (s) sdsd"

System.out.println(text.matches(pattern)) - it works
System.out.println(text2.matches(pattern)) - never ending story

出了什么问题？

Answer 1

由于正则表达式中的 *，第二个需要很长时间(或者至少可能需要很长时间，具体取决于实现)。

你的正则表达式开始尝试像这样匹配:

[a-zA-Z]+   \s* \w*      \s* \w*   \s* \w* \( \w+ \) [unmatched]
Asdadasdasd     sadsdsad     sdasd     X   (  s   )  sdsd

此时您可能希望它会说“好吧，不匹配，我们完成了”。

但这不是它的作用。

相反，它将 backtrack试图找到一个可行的匹配(因为对于计算机来说，要弄清楚在这种情况下回溯会浪费时间并不是那么容易)。

之前将第二个 \w* 与 sdasd 匹配的地方，现在它将尝试少 1 个字符，即 sdas，然后添加另一个 \s*\w*，它将匹配 \s* 的 0 个字符和 \w* 的 d。

[a-zA-Z]+   \s* \w*      \s* \w*  \s* \w* \s* \w* \( \w+ \) [unmatched]
Asdadasdasd     sadsdsad     sdas X   d       X   (  s   )  sdsd

这也不起作用，因此它会尝试 sda，然后尝试 sd，这不起作用并导致它进一步将其拆分为 sda、s 和 d。

[a-zA-Z]+   \s* \w*      \s* \w*  \s* \w* \s* \w* \( \w+ \) [unmatched]
Asdadasdasd     sadsdsad     sda  X   sd      X   (  s   )  sdsd

[a-zA-Z]+   \s* \w*      \s* \w*  \s* \w* \s* \w* \s* \w* \( \w+ \) [unmatched]
Asdadasdasd     sadsdsad     sda  X   s   X   d       X   (  s   )  sdsd

依此类推，直到每个 \w 只匹配一个字符。

PS:上面的内容不一定完全它的作用，它更多的是为了给出所发生情况的基本概念。

PPS:为简洁起见，使用 \ 而不是 \\。

如何修复它？

有几种方法可以修复它。

需要最少更改的可能是使用 (\\s*\\w*)*+ 代替 - *+ 使 * possessive ，这可以防止它回溯(这符合我们在这里想要的)。

^[a-zA-Z]+(\\s*\\w*)*+\\(\\w+\\)

也可以使用 \\s+ 而不是 \\s*，尽管这会导致一些稍微不同的行为(特别是 0-9 不能再出现在第一个空格之前，这可以通过在括号之前添加 \\w* 来修复)。

这解决了这个问题，因为我们无法再为 \\s 匹配 0 个字符，这会阻止我们在回溯时完成的大量工作。

   ^[a-zA-Z]+(\\s+\\w*)*\\(\\w+\\)
OR ^[a-zA-Z]+\\w*(\\s+\\w*)*\\(\\w+\\)

在任何一种情况下，我还建议从 [a-zA-Z] 中删除 +，因为这已经被 \\w* 覆盖(因此不会改变正则表达式匹配的内容)并且(在我看来)使正则表达式在查看时的所需行为更加清晰。

PS: [\\s]* 相当于 \\s*。