正则表达式的复杂性是什么? [英] What is the complexity of regular expression?

问题描述

在字符串上执行正则表达式比较所需的字符串长度复杂度是多少?

What is the complexity with respect to the string length that takes to perform a regular expression comparison on a string?

推荐答案

答案取决于正则表达式"的确切含义.可以将经典正则表达式编译到

The answer depends on what exactly you mean by "regular expressions." Classic regexes can be compiled into Deterministic Finite Automata that can match a string of length N in O(N) time. Certain extensions to the regex language change that for the worse.

您可能会发现以下感兴趣的文档:正则表达式匹配可以既简单又快速.

You may find the following document of interest: Regular Expression Matching Can Be Simple And Fast.

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