字符串匹配算法.ppt

《字符串匹配算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、字符串匹配算法問(wèn)題的提出記號(hào)P需尋找匹配的模式串TthetextinwhichPissoughtmthelengthofPnthelengthofT,notknowntothealgorithm,usedforanalysisonly.pi,titheithcharactersinPandTaredenotedwithlowercaselettersandsubscripts.TheinitialindexofbothPandTisassumedtobe1.jcurrentpositionwithinTkcurrentpositionwithinP一、簡(jiǎn)單字符串匹配算法P486程序二、

2、KMP算法應(yīng)用有限自動(dòng)機(jī)進(jìn)行模式匹配Definition10.2Let?bethealphabet,orsetofcharacters,fromwhichthecharacterinPandTmaybechosen,andlet?=???.Theflowchart,orfiniteautomaton,hastwotypesofnodes:Somereadnodes,whichmean“Readthenexttextcharacter.Iftherearenofurthercharacterinthetextstring,halt;thereinnomatch.”O(jiān)nereadnodei

3、sdesignatedthestartnode.Astopnode,whichmeans“Stop;amatchwasfound.”Itismarkedwitha*.Eacharrowislabeledwithacharacterfrom?.Thearrowthatmatchesthetextcharacterjustreadisthearrowtobefollowed;thatis,itindicateswhichnodetogotonext.例P488只有三個(gè)字母：A、B、C的有限狀態(tài)機(jī)流圖字符串匹配流圖readnodesmean“Readthenexttextcharacterf

4、romP”Thearrowsarecalledthesuccesslinksandthefailurelinksrespectively.例：P489KMP流圖1、與本科教材內(nèi)容之間的聯(lián)系fail[k]=max{l

5、0<=l

6、0<=l