java正则表达式产生了难以置信的重负载

Question

我有一个正则表达式，它可以在Java和在线网站中创建难以置信的高负载，帮助您测试正则表达式。正则表达式是：

import (\s*\w*\.*)*;

这对我来说很顺利

import bla.foo.bloo.blaf.blooo;

但似乎完全崩溃（只是无限地继续处理）了

import static bla.foo.bloo.somestatic.blaaaaaat.blooo.foo.*;

我想知道为什么会发生这种情况，一个修复程序正在使用

import (\s*\w*\.*\**)*;

但我不知道是什么造成了如此沉重的负担

Answer 1

我认为让它变慢的是，括号内和括号外都有星星。如果您有一个类似(\w*)*的正则表达式，并尝试匹配“foo”，那么可以通过多种方式进行匹配：

(foo)
(fo)(o)
(f)(oo)
(f)(o)(o)

（此处的括号应理解为(\w*)匹配一次）

由于正则表达式优先于深度，所以当您实际获得匹配时，这不是一个问题，但是对于不匹配的字符串，它必须通过上面的all变化，才能得出不匹配的结论

对于一个长字符串，这是一个非常多的变化。每个新字符可以继续当前的(\w*\s*\.*)或开始一个新字符，复杂性为O（2^n）

试试这一个，以获得更快的结果：import [\w\s\.]*;