匹配正则表达式时程序永远运行
我不知道为什么，但是当我尝试运行这个程序时，看起来该程序将永远运行。
package fjr.test; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Test3 { public static void main(String[] args){ String regex = "dssdfsdfdsf wdasdads dadlkn mdsds ."; Pattern p = Pattern.compile("^([a-zA-Z]+ *)+$"); Matcher match = p.matcher(regex); if(match.matches()){ System.out.println("Yess"); }else{ System.out.println("No.. "); } System.out.println("FINISH..."); } } 我需要做的是匹配包含一串只用空格分隔的单词的模式
您的程序可能遇到了所谓的灾难性回溯 。
如果你有一点时间，让我们来看看你的正则表达式如何运作……
快速复习：正则表达式如何工作：状态机始终从左到右读取，必要时回溯。
在左侧，我们有我们的模式：
/^([a-zA-Z]+ *)+$/
这是要匹配的字符串：
dssdfsdfdsf wdasdads dadlkn mdsds .
从regex101调试器，你的正则表达式失败了78540步。 这是因为你使用了贪婪 且不具有占有性的量词（回溯） 。
…长话短说，因为输入字符串无法匹配 ，正则表达式中的每个量词都会导致无限回溯 – 每个字符都从+然后被释放*然后两个然后从()+释放一个组以回溯更多。
以下是您应该遵循的一些解决方案：
避免丰富的量词！
如果你修改你的表达式，你会发现该模式在逻辑上与：
/^[a-zA-Z]+( +[a-zA-Z]+)*$/
这使用逻辑归纳的步骤来减少楼上的正则表达式以更快地匹配，现在是97步！
尽可能使用占有量词！
正如我所提到的， /^([a-zA-Z]+ *)+$/是邪恶的，因为它以可怕的方式回溯 。 我们是Java，我们能做什么？
此解决方案仅适用于[a-zA-Z]和 匹配不同的项目。 我们可以使用占有团体！
/^([a-zA-Z]++ *+)++$/ ^ ^ ^
这些简单的“ + ”表示“如果我们从这里失败，我们就不会回溯”。 这是一个非常有效的解决方案，并且不再需要回溯。 每当你有两个不同的组，其间有量词时，请使用它们。 如果你需要一些有效性的certificate，这是我们的记分卡：
阅读：
- Stack Overflow Regex参考
- ReDoS – 维基百科
在线演示：
- RegEx演示1
- RegEx演示2
这会终止，但确实需要10秒左右。 一些观察：
- 从测试字符串的末尾删除fullstop使其快速。
-
将正则表达式中的*更改为+（我相信实际上是您想要的）会使其变快。 我认为在该位置选择0个字符可以扩展状态空间。 我会用：
^（\ w + +）* \ w + $“
这意味着一堆（字空间），后跟一个字。 反对你的例子，它很快
您可以使用此正则表达式将所有单词与空格匹配或不匹配。
样品：
Pattern p = Pattern.compile("([a-zA-Z ]+)");
有趣的现象。 这与贪婪量词的行为和表现有关。
基于你的模式^([a-zA-Z]+ *)+$ ，以及你的inpput "dssdfsdfdsf wdasdads dadlkn mdsds ." ，patther与你的输入不匹配，但是，java正则表达式将回溯^([a-zA-Z]+ *)+所有可能性（见下面的例子），然后获得不匹配的结果。
(dssdfsdfdsf )(wdasdads )(dadlkn )(mdsds ) (dssdfsdfdsf )(wdasdads )(dadlkn )(mdsd)(s ) (dssdfsdfdsf )(wdasdads )(dadlkn )(mds)(ds ) ... (d)(s)(s)(d)(f)(s)(d)(f)(d)(s)(f )(w)(d)(a)(s)(d)(a)(d)(s )(d)(a)(d)(l)(k)(n )(m)(d)(s)(d)(s ) ... (dssdfsdfdsf ) ... (d)
回溯可能超过200,000,000次。
我有点好奇为什么java-regex不能做一些性能提升，因为在第一次尝试之后，它发现epxected char是’。’而不是’$’，那么任何进一步的回溯都不会成功。 做回溯是没用的。
因此，当我们定义循环模式时，我们需要更多地关注内部循环模式（例如：在您的示例中为[a-zA-Z]+ * ），而不是使它匹配如此多的情况。 否则，整个Loop的回溯数将是巨大的。
另一个类似的例子（比你的情况更糟糕）：
模式 ：“（。+）* A”
输入 ：“abcdefghijk lmnopqrs tuvwxy zzzzz A” – 这么快
输入 ：“abcdefghijAk lmnopqrs tuvwxy zzzzz” – 还不错，等一会儿
输入 ：“aAbcdefghijk lmnopqrs tuvwxy zzzzz” – 似乎无限。 （实际上，不是，但我没有耐心等待它的完成。）