Posted on 2008-03-27 00:21
ZelluX 閱讀(1699)
評論(0) 編輯 收藏 所屬分類:
Algorithm
其實理解了?Regular Expression?-> NFA -> DFA 這個過程，大致的復(fù)雜度確定也不難
發(fā)信人: styc (styc), 信區(qū): Algorithm
標(biāo)? 題: Re: 請問一下大家正則表達(dá)式的時間復(fù)雜度
發(fā)信站: 水木社區(qū) (Wed Mar 26 20:37:02 2008), 站內(nèi)
NFA構(gòu)造O(n)，匹配O(nm)
DFA構(gòu)造O(2^n)，最小化O(kn'logn')（N'=O(2^n)），匹配O(m)
n=regex長度，m=串長，k=字母表大小，n'=原始的dfa大小
大概是這樣子吧