regex - 子字符串与正则表达式匹配更快？

Question

在阅读了 RE/NFA 和 DFA 之后，似乎使用 RE 而不是蛮力 O(mn) 查找在字符串中查找子字符串实际上可能会渐近地更快。我的推理是 DFA 实际上会维护状态并避免多次处理“大海捞针”中的每个字符。因此，如果使用正则表达式，长字符串中的搜索实际上可能会快得多。

当然，这仅对从 NFA 转换为 DFA 的 RE 匹配器有效。

当使用 RE 而不是蛮力匹配器时，是否有人在现实生活中体验过更好的字符串匹配性能？

Answer 1

实践中使用的大多数正则表达式是 PCRE(Perl-Compatible Regular Expressions)，它比正则语言更宽，因此不能用正则文法表达。 PCRE 具有正/负前瞻/后视断言甚至递归之类的功能，因此解析可能需要多次处理某些字符。当然，这一切都归结为特定的 RE 实现:如果表达式保持在正则语法的范围内，是否对其进行了优化。

就个人而言，我还没有对两者进行任何形式的性能比较。然而，根据我的经验，我从来没有遇到过蛮力查找和替换的性能问题，而我不得不不止一次处理 RE 性能瓶颈。