为什么 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 时间是：

看起来复杂度是 O( 3^n )

为什么会这样？是不是我的表达有问题？

如果我使用像“1 a 1”这样的字符串，虽然常数较小，但增长因子是相同的。

编辑：我看到问题是我遇到了 .*+ 哎呀！我仍然不确定为什么这会导致指数行为。

Answer 1

我认为正则表达式引擎只想找到任何 .* 1 次，因为 +。这已经是无穷无尽的了，所以引擎会在一段时间后取消操作。

Answer 2

问题是 .*+\b 而不是 .*\b 我很确定你想要的。

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

由于它不知道整体应该匹配多少个字符，它会尝试所有可能的组合，直到到达最后一个，发现它们都匹配相同长度的字符串，并宣布整体失败（因为你有一个 \b 这是一个反 space 字符，它不存在于你的输入字符串中）。根据您是使用 NFA 还是 DFA 进行正则表达式匹配，您可能会得到您观察到的可怕行为，或者您可能会得到完全线性的行为——或者（取决于您如何进行 DFA/NFA 转换）它可能只是无法编译正则表达式（这可能不太符合要求，但仍然可能是更可取的行为）。

为什么 Regex (c++) 需要指数时间？

Why is Regex (c++) taking exponential time?

c++

regex

time-complexity

clock