资源描述：
《Basic_KMP_SIAM_JNL_Comp_77_KMP_string_matching.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、SIAMJ.COMPUT.Vol.6,No.2,June1977FASTPATTERNMATCHINGINSTRINGS*DONALDE.KNUTHf,JAMESH.MORRIS,JR.:l:ANDVAUGHANR.PRATTAbstract.Analgorithmispresentedwhichfindsalloccurrencesofone.givenstringwithinanother,inrunningtimeproportionaltothesumofthelengthsofthestrings.Theconstantofproportionalityislowenoughto
2、makethisalgorithmofpracticaluse,andtheprocedurecanalsobeextendedtodealwithsomemoregeneralpattern-matchingproblems.Atheoreticalapplicationofthealgorithmshowsthatthesetofconcatenationsofevenpalindromes,i.e.,thelanguage{can}*,canberecognizedinlineartime.Otheralgorithmswhichrunevenfasterontheaveragear
3、ealsoconsidered.Keywords,pattern,string,text-editing,pattern-matching,triememory,searching,periodofastring,palindrome,optimumalgorithm,Fibonaccistring,regularexpressionText-editingprogramsareoftenrequiredtosearchthroughastringofcharacterslookingforinstancesofagiven"pattern"string;wewishtofindallpo
4、sitions,orperhapsonlytheleftmostposition,inwhichthepatternoccursasacontiguoussubstringofthetext.Forexample,caenarycontainsthepatternen,butwedonotregardcanaryasasubstring.Theobviouswaytosearchforamatchingpatternistotrysearchingateverystartingpositionofthetext,abandoningthesearchassoonasanincorrectc
5、haracterisfound.Butthisapproachcanbeveryinefficient,forexamplewhenwearelookingforanoccurrenceofaaaaaaabinaaaaaaaaaaaaaab.Whenthepatternisa"bandthetextisa2"b,wewillfindourselvesmaking(n+1)comparisonsofcharacters.Furthermore,thetraditionalapproachinvolves"backingup"theinputtextaswegothroughit,andthi
6、scanaddannoyingcomplicationswhenweconsiderthebufferingoperationsthatarefrequentlyinvolved.Inthispaperwedescribeapattern-matchingalgorithmwhichfindsalloccurrencesofapatternoflengthrnwithinatextoflengthninO(rn+n)unitsoftime,without"backingup"theinputtext.ThealgorithmneedsonlyO(m)locationsofinternalm
7、emoryifthetextisreadfromanexternalfile,andonlyO(logm)unitsoftimeelapsebetweenconsecutivesingle-characterinputs.Alloftheconstantsofproportionalityimpliedbythese"O"formulasareindependentofthealphabetsize.*Receivedb
