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

前端之家收集整理的这篇文章主要介绍了平均正则表达式算法的时间复杂度是多少?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我不是使用正则表达式的新手,我理解他们基于有限状态机的基本理论。

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

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

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

猜你在找的正则表达式相关文章