什么是平均正则表达式算法的时间复杂度？ [英] What's the Time Complexity of Average Regex algorithms?

问题描述

我是不是新来使用常规的前pressions，我明白的基本的理论他们依据 - 有限状态机。

I'm not new to using regular expressions, and I understand the basic theory they're based on--finite state machines.

我不是在算法分析虽然这么好，不明白一个正则表达式进行比较说，一个基本的线性搜索。我问，因为表面上这似乎是一个线性阵列搜索。 （如果正则表达式是简单的。）

I'm not so good at algorithmic analysis though and don't understand how a regex compares to say, a basic linear search. I'm asking because on the surface it seems like a linear array search. (If the regex is simple.)

在哪里我能去更多地了解实现正则表达式引擎？

Where could I go to learn more about implementing a regex engine?

推荐答案

这是最流行的轮廓之一：常规防爆pression匹配可以简单快速 。运行针对一个字符串DFA编译常规的前pression确实为O（n），但可能需要最多O（2 ^米）施工时间/空间（其中m =普通EX pression大小）。

This is one of the most popular outlines: Regular Expression Matching Can Be Simple And Fast . Running a DFA-compiled regular expression against a string is indeed O(n), but can require up to O(2^m) construction time/space (where m = regular expression size).

这篇关于什么是平均正则表达式算法的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！