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

问题描述

我对使用正则表达式并不陌生，而且我理解它们基于的基本理论——有限状态机.

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?

推荐答案

这是最流行的大纲之一:正则表达式匹配既简单又快速.针对字符串运行 DFA 编译的正则表达式确实是 O(n)，但可能需要最多 O(2^m) 的构造时间/空间(其中 m = 正则表达式大小).

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屋！