字符串匹配算法.ppt

《字符串匹配算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、字符串匹配算法问题的提出记号P需寻找匹配的模式串TthetextinwhichPissoughtmthelengthofPnthelengthofT,notknowntothealgorithm,usedforanalysisonly.pi,titheithcharactersinPandTaredenotedwithlowercaselettersandsubscripts.TheinitialindexofbothPandTisassumedtobe1.jcurrentpositionwithinTkcurrentpositionwithinP一、简单字符串匹配算法P486程序二、

2、KMP算法应用有限自动机进行模式匹配Definition10.2Letbethealphabet,orsetofcharacters,fromwhichthecharacterinPandTmaybechosen,andlet=.Theflowchart,orfiniteautomaton,hastwotypesofnodes:Somereadnodes,whichmean“Readthenexttextcharacter.Iftherearenofurthercharacterinthetextstring,halt;thereinnomatch.”Onereadnodei

3、sdesignatedthestartnode.Astopnode,whichmeans“Stop;amatchwasfound.”Itismarkedwitha*.Eacharrowislabeledwithacharacterfrom.Thearrowthatmatchesthetextcharacterjustreadisthearrowtobefollowed;thatis,itindicateswhichnodetogotonext.例P488只有三个字母：A、B、C的有限状态机流图字符串匹配流图readnodesmean“Readthenexttextcharacterf

4、romP”Thearrowsarecalledthesuccesslinksandthefailurelinksrespectively.例：P489KMP流图1、与本科教材内容之间的联系fail[k]=max{l

5、0<=l

6、0<=l