saving comparisons in the crochemore-perrin string matching algorithm

《saving comparisons in the crochemore-perrin string matching algorithm》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SavingComparisonsintheCrochemore-PerrinStringMatchingAlgorithm(preliminaryversion)DanyBreslauerCWICUCS-052-92AbstractCrochemoreandPerrindiscoveredanelegantlinear-timeconstant-spacestringmatchingalgorithmthatmakesatmost2n?msymbolcomparison.Thispapershowshowtomodifyt

2、heiralgorithmtousefewercomparisons.Givenanyxed>0,themodiedalgorithmtakeslineartime,usesconstantspace1+andmakesatmostn+b(n?m)ccomparisons.IfO(logm)spaceisavailable,then21thealgorithmmakesatmostn+b(n?m)ccomparisons.Thepatternpreprocessing2stepalsotakeslineartimean

3、dusesconstantspace.Thesearetherststringmatchingalgorithmsthatmakefewerthan2n?mcom-parisonsandusesub-linearspace.1IntroductionStringmatchingistheproblemofndingalloccurrencesofashortstringP[1::m]thatiscalledapatterninalongerstringT[1::n]thatiscalledatext.Tosolvethes

4、tringmatchingproblemonehasonlytobeabletocomparesymbolsoftheinputstrings.Inthispaperwestudytheexactcomparisoncomplexityofthestringmatchingproblem.Weassumethattheonlyaccessanalgorithmhastotheinputstringsisbypairwisesymbolcomparisonsthatresultinequalorunequalanswers.Se

5、veralalgorithmssolvethestringmatchingprobleminlineartime.ForasurveyonstringmatchingalgorithmseeAho'spaper[1].MostknownperhapsisthealgorithmofKnuth,MorrisandPratt[20]thatmakes2n?mcomparisonsintheworstcase.AvariantoftheBoyer-Moore[4]algorithmthatwasdesignedbyApostolic

6、oandGiancarlo[2]alsomakes2n?PartiallysupportedbytheIBMGraduateFellowshipwhilestudyingatColumbiaUniversityandbytheEuropeanResearchConsoriumforInformaticsandMathematicspostdoctoralfellowship.PartoftheworkwasdonewhilethisauthorwasvisitingatUniversitadeL'Aquila,L'Aqui

7、la,Italyinsummer1991.1mcomparisons.TheoriginalBoyer-Moorealgorithmmakesabout3ncomparisonsasshownrecentlybyCole[7].Allthesealgorithmsworkintwosteps:intherststepthepatternispreprocessedandsomeinformationisstoredandusedlaterinatextprocessingstep.Ourboundsdonotaccountf

8、orcomparisonsthatareperformedinthepatternpreprocessingstepthatcancompareevenallpairsofpatternsymbolsforfree.Researchontheexactnumberofcomp