c# - 正则表达式性能问题 - 任何人都可以解释这个正则表达式很慢的方式

Question

我正在尝试使用 regex 实现 String.Contains() 方法。我注意到这个模式 @".\*foo.\*" 比这个 @"\A.\*foo.\*\Z".

谁能解释一下为什么？

Answer 1

因为没有 anchor ，正则表达式引擎必须进行更多次匹配尝试才能断定匹配是不可能的。考虑一个带有 anchor 的例子:

Regex: \A.*foo.*\Z
Input: 123456789abcdef

正则表达式会看到输入 anchor 的开头并将其考虑在内。它现在尝试匹配第一个 .* 模式，并且由于它是贪婪的，所以它尝试匹配所有输入。然后它尝试匹配 foo 并失败，因此它从 .* 匹配中释放 f 并再次尝试。它再次失败，从 .* 匹配中释放 e，再次尝试，失败，等等。

最终结果是整个表达式无法匹配之前所进行的尝试次数与输入长度线性。

现在考虑非锚定情况:

Regex: .*foo.*
Input: 123456789abcdef

这一次，正则表达式引擎尝试从字符串的开头开始匹配，如上(与字符串长度的尝试次数成线性关系)。但是当失败时，它会从输入的第二个字符开始再次开始这个过程。

也就是说，它尝试将第一个 .* 与以下内容相继匹配:

123456789abcdef
123456789abcde
123456789abcd
...
1
                  (empty string due to the * quantifier)

到目前为止，这与锚定正则表达式相同。但是，虽然此时 anchor 会导致匹配失败，但非锚定正则表达式会继续尝试

23456789abcdef
23456789abcde
23456789abcd
...
2
                  (empty string due to the * quantifier)

如您所见，这次在整个表达式无法匹配之前所进行的尝试次数是输入长度的二次。