为什么Regex(c ++)采用指数时间？

Question

我正在从教科书中做一些正则表达式问题,他们会阅读以下内容:

"[匹配]从行开头开始的所有字符串都带有一个整数,并以一个单词结束在该行的末尾."

我为此写了以下正则表达式:

^[0-9]+\s.*+\b[a-zA-Z]+$

但是,当我使用以下代码在C++中实现它时:

#include <iostream>
#include <string>
#include <regex>
#include <time.h>

int main(){
    clock_t t;
    bool match;
    std::string exp = "^[0-9]+\\s.*+\b[a-zA-Z]+$";
    std::string str = "1 a few words 1";
    std::string s (str);
    std::smatch m;
    std::regex e (exp);
    while (true){
        t = clock();
        match = std::regex_match(s, m, e); 
        s = s + "1";
        std::cout << clock() - t << std::endl;
    }   
}

每次迭代所花费的CPU时间是:

1 1181529
2 3398674
3 10102763
4 30370932
5 92491242

看起来很复杂 O( 3^n )

为什么会这样？在表达中有什么我做错了吗？

如果我使用像"1 a 1"这样的字符串,但是使用较小的常量,则增长因子是相同的.

编辑:我看到的问题是我有一个.*+哎呀!我仍然不确定为什么会导致指数行为.

Answer 1

问题在于,.*+\b而不是.*\\b我非常确定你的意图.

至于为什么会导致可怕的行为:问题是.*可以算一些任意数量的字符,并且+意味着匹配任意数量的字符.但是,为了适应POSIX规范,它必须尽可能使整个模式匹配尽可能长的字符串.我的猜测是,要做到这一点,首先要尝试使用.*匹配一个字符,并重复N次.然后它尝试.*匹配两个字符,并重复M次.然后它尝试使用.*匹配的三个字符,并重复它们L次(依此类推).哦,请注意,它不必使所有.*模式都匹配相同数量的字符,因此组合的数量呈指数增长.

由于它不知道它应该总共匹配多少个字符,它会尝试每个可能的组合,直到它到达最后一个,发现它们都匹配相同长度的字符串,并声明它是一个整体失败(因为你有一个\b是输入字符串中不存在的后退字符).根据您是使用NFA还是DFA进行正则表达式匹配,您可能会遇到您观察到的可怕行为,或者您可能获得完全线性行为 - 或者(取决于您执行DFA/NFA转换的方式)它可能只是无法编译正则表达式(这可能不太符合,但仍然可能是更好的行为).