对字符串执行正则表达式比较所需的字符串长度的复杂性是多少?
答案取决于“正则表达式”的确切含义。经典的正则表达式可以是compiled into 确定性有限自动机可以匹配长度的字符串N in O(N)时间。正则表达式语言的某些扩展使情况变得更糟。
N
O(N)
您可能会发现以下感兴趣的文档:正则表达式匹配可以简单而快速.