Ahm*_*rid 69 regex complexity-theory big-o
在字符串上执行正则表达式比较所需的字符串长度的复杂性是多少？
NPE*_*NPE 62
答案取决于"正则表达式"究竟是什么意思.经典的正则表达式可以被编译成确定性有限自动机可以匹配长度的字符串N中O(N)的时间.正则表达式语言的某些扩展会改变这种情况.
N
O(N)
您可以找到以下感兴趣的文档:正则表达式匹配可以简单快速.
Ale*_*own 9
unbounded - 您可以在空输入字符串上创建一个永不终止的正则表达式.
小智 6
如果你使用普通(TCS:没有反向引用,连接,交替,Kleene星)regexp和regexp已经编译,那么它是O(n).
归档时间：
14 年，11 月 前
查看次数：
26749 次
最近记录：
6 年，7 月 前