Posted on 2008-03-27 00:21
ZelluX 閱讀(1694)
評(píng)論(0) 編輯 收藏 所屬分類:
Algorithm
其實(shí)理解了?Regular Expression?-> NFA -> DFA 這個(gè)過程，大致的復(fù)雜度確定也不難
發(fā)信人: styc (styc), 信區(qū): Algorithm
標(biāo)? 題: Re: 請(qǐng)問一下大家正則表達(dá)式的時(shí)間復(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長(zhǎng)度，m=串長(zhǎng)，k=字母表大小，n'=原始的dfa大小
大概是這樣子吧