作者:羊鲜鸡美蟹肥 | 来源:互联网 | 2022-12-10 13:18
我正在从教科书中做一些正则表达式问题,他们会阅读以下内容:
"[匹配]从行开头开始的所有字符串都带有一个整数,并以一个单词结束在该行的末尾."
我为此写了以下正则表达式:
^[0-9]+\s.*+\b[a-zA-Z]+$
但是,当我使用以下代码在C++中实现它时:
#include
#include
#include
#include
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 <
每次迭代所花费的CPU时间是:
1 1181529
2 3398674
3 10102763
4 30370932
5 92491242
看起来很复杂 O( 3^n )
为什么会这样?在表达中有什么我做错了吗?
如果我使用像"1 a 1"这样的字符串,但是使用较小的常量,则增长因子是相同的.
编辑:我看到的问题是我有一个.*+
哎呀!我仍然不确定为什么会导致指数行为.
1> Jerry Coffin..:
问题在于,.*+\b
而不是.*\\b
我非常确定你的意图.
至于为什么会导致可怕的行为:问题是.*
可以算一些任意数量的字符,并且+
意味着匹配任意数量的字符.但是,为了适应POSIX规范,它必须尽可能使整个模式匹配尽可能长的字符串.我的猜测是,要做到这一点,首先要尝试使用.*
匹配一个字符,并重复N次.然后它尝试.*
匹配两个字符,并重复M次.然后它尝试使用.*
匹配的三个字符,并重复它们L次(依此类推).哦,请注意,它不必使所有.*
模式都匹配相同数量的字符,因此组合的数量呈指数增长.
由于它不知道它应该总共匹配多少个字符,它会尝试每个可能的组合,直到它到达最后一个,发现它们都匹配相同长度的字符串,并声明它是一个整体失败(因为你有一个\b
是输入字符串中不存在的后退字符).根据您是使用NFA还是DFA进行正则表达式匹配,您可能会遇到您观察到的可怕行为,或者您可能获得完全线性行为 - 或者(取决于您执行DFA/NFA转换的方式)它可能只是无法编译正则表达式(这可能不太符合,但仍然可能是更好的行为).
@Kevin:正则表达式引擎将解释反斜杠的双字符序列,然后是&#39;b`作为单词边界,是的.但是在源代码中只有`\ b`它不会接收到 - 编译时编译器将`\ b`转换为单个后退字符.要在正则表达式中使用`\ b`,您要在字符串中使用`\\ b`,或使用原始字符串来防止转义字符转换.