匹配正则表达式时程序永远运行

Question

我不知道为什么,但是当我尝试运行这个程序时,看起来该程序将永远运行.

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..."); 
    }

}

我需要做的是匹配包含一串只用空格分隔的单词的模式

Answer 1

您的程序可能遇到了所谓的灾难性回溯.

如果你有一点时间,让我们来看看你的正则表达式如何工作......

_{快速复习:正则表达式如何工作:状态机始终从左到右读取,必要时回溯.}

在左侧,我们有我们的模式:

/^([a-zA-Z]+ *)+$/

这是要匹配的字符串:

dssdfsdfdsf wdasdads dadlkn mdsds .

从regex101调试器,你的正则表达式需要78540步才能失败.这是因为你使用了贪婪而不是占有欲的量词(回溯).

...长话短说,因为输入字符串无法匹配,正则表达式中的每个量词都会导致无限回溯 - 每个字符都会被释放+,然后*然后两者都被释放,然后一个组被释放出来()+以回溯更多.

以下是您应该遵循的一些解决方案:

避免丰富的量词!

如果您修改表达式,您将看到该模式在逻辑上与以下相同:

/^[a-zA-Z]+( +[a-zA-Z]+)*$/

这里使用的步骤,逻辑归纳,减少楼上正则表达式匹配远在97步快,现在!

尽可能使用占有量词!

正如我所提到的,/^([a-zA-Z]+ *)+$/它是邪恶的,因为它以可怕的方式回溯.我们是Java,我们能做什么？

此解决方案仅是因为[a-zA-Z]和 matches distinct items. We can use a possessive group!

/^([a-zA-Z]++ *+)++$/
            ^  ^  ^

These simple "+"表示"如果我们从这里失败,我们就不会回溯".这是一个非常有效的解决方案,并且不再需要回溯.每当你有两个不同的组,其间有量词时,请使用它们.如果您需要有关效果的证据,这是我们的记分卡:

阅读:

• Stack Overflow Regex参考
• ReDoS - 维基百科

在线演示:

• RegEx演示1
• RegEx演示2