算法导论-ch32 string matching.ppt

Ch32StringMatchingIntroductionNaïveAlgorithmRabin-KarpAlgorithm StringMatchingusingFiniteAutomataKnuth-Morris-Pratt(KMP)AlgorithmLiteratureCormen,Leiserson,Rivest,“IntroductiontoAlgorithms”,chapter32,stringmatching,TheMITPress,2001,906-?urrencesofapatterninagiventext(orbodyoftext)ManyapplicationsWhileusingeditor/wordprocessor/browserLoginname&municationsDNAsequenceanalysis2HistoryofStringSearchThebruteforcealgorithm:puterhistoryre-inventedmanytimes,monKnuth&Prattinventedabetteronein1970published1976as“Knuth-Morris-Pratt”Boyer&Moorefoundabetteronebefore1976Published1977Karp&Rabinfounda“better”onein1980Published19873String-MatchingProblemThetextisinanarrayT[1..n]oflengthnThepatternisinanarrayP[1..m]oflengthmElementsofTandParecharactersfromafinitealphabet.,={0,1}or={a,b,…,z}UsuallyTandParecalledstringsofcharacters4String-MatchingProblem…urswithshiftsintextTif: 0≤s≤n-mandT[(s+1)..(s+m)]=P[1..m]urswithshiftsinT,thensisavalidshift,otherwisesisaninvalidshiftString-matchingproblem:findingallvalidshiftsforagivenTandP5Example1abcabaabcabacabaatextTpatternPs=3shifts=3isavalidshift(n=13,m=4and0≤s≤n-mholds)12345678910**********Example2abcabaabcabaaabaatextTpatternPs=3abaaabaas=912345678910**********NaïveString-MatchingAlgorithmInput:TextstringsT[1..n]andP[1..m]Result:AllvalidshiftsdisplayedNAÏVE-STRING-MATCHER(T,P) n←length[T] m←length[P] fors←0ton-m ifP[1..m]=T[(s+1)..(s+m)] print“urswithshift”s8ExampleP=“abxyabxz”andT=“xabxyabxyabxz”xazxbaybxyabxTzxbabxyaPabxyabxzazbxyabxzxabxyabzxbabxyazxbaabxyzxbayabx9Worst-parisonsforeachshiftintheworstcaseTherearen-m+1shiftsSo,theworst-caserunningtimeisΘ((n-m+1)m)Naïvemethodisinefficientbecauseinformationfromashiftisnotusedagain10