对于给定长度的正则表达式模式，google 的 re2 的时间复杂度
Time complexity of google's re2 for a given length of regex pattern
我正在研究 google 的 re2 实现，我想使用一些不受信任的来源提供的正则表达式进行正则表达式匹配。我浏览了以下资源 -
使用 PCRE，我们可以处理一些非常糟糕的情况，并且可能需要指数时间来匹配。例如对于正则表达式 (.*)+b 和像 aaaaaaaaa... 这样的字符串，它可能需要 O(c^n) 时间，其中 n 是字符串的长度。
记录了更多 DOS 表达式 here.
我知道 re2 将在线性时间内针对给定的正则表达式与给定长度的字符串进行匹配。现在，我的问题是，如果我能够在 re2 中编译正则表达式，并且我对正则表达式模式的长度施加了限制，那么我能保证它不会 运行 进入某些 DOS上面提到的情况 link 或其他一些正则表达式模式？
re2 对于给定长度 n 的字符串，具有 O(n) 的最坏情况复杂度，这与支持 backtracking/look领先。
所以只要字符串的长度和正则表达式的长度都被限制了，并且你事先验证了正则表达式，re2 就不能被 DOSed。
但是在从 PCRE 迁移某些模式或以其他方式使用它时，您需要确保可以编译正则表达式模式，因为该实现不支持许多 PCRE 功能，例如反向引用。
我正在研究 google 的 re2 实现，我想使用一些不受信任的来源提供的正则表达式进行正则表达式匹配。我浏览了以下资源 -
使用 PCRE，我们可以处理一些非常糟糕的情况，并且可能需要指数时间来匹配。例如对于正则表达式 (.*)+b 和像 aaaaaaaaa... 这样的字符串，它可能需要 O(c^n) 时间，其中 n 是字符串的长度。
记录了更多 DOS 表达式 here.
我知道 re2 将在线性时间内针对给定的正则表达式与给定长度的字符串进行匹配。现在，我的问题是，如果我能够在 re2 中编译正则表达式，并且我对正则表达式模式的长度施加了限制，那么我能保证它不会 运行 进入某些 DOS上面提到的情况 link 或其他一些正则表达式模式？
re2 对于给定长度 n 的字符串，具有 O(n) 的最坏情况复杂度，这与支持 backtracking/look领先。
所以只要字符串的长度和正则表达式的长度都被限制了，并且你事先验证了正则表达式，re2 就不能被 DOSed。
但是在从 PCRE 迁移某些模式或以其他方式使用它时，您需要确保可以编译正则表达式模式，因为该实现不支持许多 PCRE 功能，例如反向引用。