资源描述：
《Fast String Matching algo compare.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、SHIPPENSBURGUNIVERSITYFastStringMatchingAlgorithmsComparedRabin-Karpvs.Knuth-Morris-Prattvs.Boyer-Moore-HorspoolEricC.Abruzzese4/21/2011TheAlgorithmsKnuth-Morris-PrattReferencesUsedKNUTHD.E.,MORRIS(Jr)J.H.,PRATTV.R.,1977,Fastpatternmatchinginstrings,S
2、IAMJournalonComputing6(1):323-350DescriptionoftheAlgorithmTheKnuth-Morris-Pratt(KMP)algorithmeliminatestheinefficienciesofthebrute-forceapproachbyreducingthewastedinformationobtainedasweperformasearch.TheKMPalgorithmbeginsbypreprocessingthegivenpatter
3、nandcomputinga“failurefunction”(theresultsofwhicharestoredinatable)thatindicatesthelargestshiftusingpreviouslyperformedcomparisons.Essentially,wearecomputingthelengthofthelongestprefixofthepatternthatisalsoasuffixofthesamepattern.Aftercomputingthefail
4、urefunction,wematchthepatternfromrighttoleft(alaHorspool),tothegiventext.Uponobservingamismatch,welookinthetableofcomputedshiftingvaluesandshiftthatmanytotheright.ThisalgorithmisessentiallyanattempttoimproveontheMorris-Prattalgorithmbyincreasingthesiz
5、eofshiftswhenamismatchoccurs.ClaimedEfficiency:O(n+m)Pseudocode(CLanguage):voidpreKmp(char*x,intm,intkmpNext[]){inti,j;i=0;j=kmpNext[0]=-1;while(i-1&&x[i]!=x[j])j=kmpNext[j];i++;j++;if(x[i]==x[j])kmpNext[i]=kmpNext[j];elsekmpNext[i]=j;}}vo
6、idKMP(char*x,intm,char*y,intn){inti,j,kmpNext[XSIZE];/*Preprocessing*/preKmp(x,m,kmpNext);/*Searching*/i=j=0;while(j-1&&x[i]!=y[j])i=kmpNext[i];i++;j++;if(i>=m){OUTPUT(j-i);i=kmpNext[i];}}}Rabin-KarpReferencesUsedKARPR.M.,RABINM.O.,1987,Ef
7、ficientrandomizedpattern-matchingalgorithms.IBMJ.Res.Dev.31(2):249-260.LECROQ,T.,1995,Experimentalresultsonstringmatchingalgorithms,Software-Practice&Experience25(7):727-765.DescriptionoftheAlgorithmTheRabin-Karpalgorithmisoneofrelativeinterestbecause
8、itusestheefficiencyadvantagesofahashtableandappliesthemtostringmatching.Thealgorithmworksbyusinganefficientlycomputable,highlydiscriminatinghashfunctionthatisusedtodeterminehowcloselyrelatedthepatternandthecurrentword(searchwindow)are(essentia
