使用 ICU 4.0 正则表达式库,我发现以下正则表达式表现出指数时间:
actual: "[^<]*<\?"
C code: "[^<]*<\\?"
目标:找到“”在它之前没有其他“<”
当在没有“<”字符的纯文本上运行这个正则表达式时,它似乎需要指数时间。如果文本至少有一个“<”,那么它很快。我不明白为什么。
不应该匹配“<?”防止这需要回溯?我原以为它会尝试找到第一个“<”,然后测试表达式的其余部分。如果它找不到“<”,那么它会放弃,因为模式显然无法匹配。
这是 ICU 正则表达式中的错误还是预期中的错误?
最佳答案
你会在 Regular Expression Matching Can Be Simple And Fast 找到解释.
正如 MizardX 所说,如果匹配在位置 0 处失败,引擎将在位置 1、2 等处重试。如果文本很长,请准备好等待一段时间......
解决方法是 anchor 定你的表情:"^[^<]*<\?"
关于regex - 当文本没有 "[^<]*<\\?"时,为什么正则表达式 "<"表现出指数时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/313900/