regex - 当文本没有 "[^<]*<\\?"时，为什么正则表达式 "<"表现出指数时间？

Question

使用 ICU 4.0 正则表达式库，我发现以下正则表达式表现出指数时间:

actual: "[^<]*<\?"
C code: "[^<]*<\\?"

目标:找到“
当在没有“<”字符的纯文本上运行这个正则表达式时，它似乎需要指数时间。如果文本至少有一个“<”，那么它很快。我不明白为什么。

不应该匹配“<？”防止这需要回溯？我原以为它会尝试找到第一个“<”，然后测试表达式的其余部分。如果它找不到“<”，那么它会放弃，因为模式显然无法匹配。

这是 ICU 正则表达式中的错误还是预期中的错误？

Answer 1

你会在 Regular Expression Matching Can Be Simple And Fast 找到解释.
正如 MizardX 所说，如果匹配在位置 0 处失败，引擎将在位置 1、2 等处重试。如果文本很长，请准备好等待一段时间......

解决方法是 anchor 定你的表情:"^[^<]*<\?"