资源描述：
《Basic_BM_A Fast String Searching Algorithm.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1.IntroductionSupposethatpatisastringoflengthpatlenandwewishtofindthepositionioftheleftmostcharacterinProgrammingG.Manacher,S.L.Grahamthefirstoccurrenceofpatinsomestringstring:TechniquesEditorspat:AT-THATAFastStringstring:...WHICH-FINALLY-HALTS.--AT-THAT-POINT...Theobvioussearchalgorithmcons
2、iderseachcharacterSearchingAlgorithmpositionofstringanddetermineswhetherthesucces-sivepatlencharactersofstringstartingatthatpositionRobertS.Boyermatchthesuccessivepatlencharactersofpat.Knuth,StanfordResearchInstituteMorris,andPratt[4]haveobservedthatthisalgorithmisquadratic.Thatis,intheworst
3、case,thenumberofJStrotherMoorecomparisonsisontheorderofi*patlen.lXeroxPaloAltoResearchCenterKnuth,Morris,andPratthavedescribedalinearsearchalgorithmwhichpreprocessespatintimelinearinpatlenandthensearchesstringintimelinearini+Analgorithmispresentedthatsearchesforthepatlen.Inparticular,theiral
4、gorithminspectseachoflocation,"i,"ofthefirstoccurrenceofacharacterthefirsti+patlen-1charactersofstringpreciselystring,"'pat,'"inanotherstring,"string."Duringtheonce.searchoperation,thecharactersofpatarematchedWenowpresentasearchalgorithmwhichisusuallystartingwiththelastcharacterofpat.Theinfo
5、rmation"sublinear":Itmaynotinspecteachofthefirsti+gainedbystartingthematchattheendofthepatternpatlen-1charactersofstring.By"usuallysublinear"oftenallowsthealgorithmtoproceedinlargejumpswemeanthattheexpectedvalueofthenumberofthroughthetextbeingsearched.Thusthealgorithminspectedcharactersinstr
6、ingisc*(i+patlen),wherehastheunusualpropertythat,inmostcases,notallofc<1andgetssmalleraspatlenincreases.Therearethefirsticharactersofstringareinspected.Thepatternsandstringsforwhichworsebehaviorisex-numberofcharactersactuallyinspected(ontheaver-hibited.However,Knuth,in[5],hasshownthattheage)
7、decreasesasafunctionofthelengthofpat.Foraalgorithmislinearevenintheworstcase.randomEnglishpatternoflength5,thealgorithmwillTheactualnumberofcharactersinspecteddependstypicallyinspecti/4charactersofstringbeforefindingonstatisticalpropertiesofthechar
