平均正则表达式算法的时间复杂度是多少？

发布时间：2020-12-14 06:39:16 所属栏目：百科来源：网络整理

导读：我不是使用正则表达式的新手，我理解他们基于有限状态机的基本理论。我不是那么好的算法分析，但不明白一个正则表达式如何比较说，一个基本的线性搜索。我问，因为在表面上看起来像一个线性数组搜索。 (如果正则表达式很简单。) 在哪里可以了解更多关于实现

我不是使用正则表达式的新手，我理解他们基于有限状态机的基本理论。

我不是那么好的算法分析，但不明白一个正则表达式如何比较说，一个基本的线性搜索。我问，因为在表面上看起来像一个线性数组搜索。 (如果正则表达式很简单。)

在哪里可以了解更多关于实现正则表达式引擎？

这是最流行的概要之一： Regular Expression Matching Can Be Simple And Fast .对字符串运行DFA编译的正则表达式确实是O(n)，但是可能需要最多O(2 ^ m)构造时间/空间(其中m =正则表达式大小)。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!