kmp算法[英文详解](转)

《kmp算法[英文详解](转)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Knuth-Morris-PrattstringmatchingTheproblem:givena(short)patternanda(long)text,bothstrings,determinewhetherthepatternappearssomewhereinthetext. Lasttime wesawhowtodothiswithfiniteautomata.Thistimewe'llgothroughthe Knuth-Morris-Pratt (KMP)algorithm,whichcanbethoughtofasaneffici

2、entwaytobuildtheseautomata.Ialsohavesome workingC++sourcecodewhichmighthelpyouunderstandthealgorithmbetter.Firstlet'slookatanaivesolution.supposethetextisinanarray:charT[n]andthepatternisinanotherarray:charP[m].Onesimplemethodisjusttotryeachpossiblepositionthepatterncouldappe

3、arinthetext.Naivestringmatching:for(i=0;T[i]!='';i++){for(j=0;T[i+j]!=''&&P[j]!=''&&T[i+j]==P[j];j++);if(P[j]=='')foundamatch}Therearetwonestedloops;theinneronetakesO(m)iterationsandtheouteronetakesO(n)iterationssothetotaltimeistheproduct,O(mn).Thisisslow;we'dliketosp

4、eeditup.Inpracticethisworksprettywell--notusuallyasbadasthisO(mn)worstcaseanalysis.Thisisbecausetheinnerloopusuallyfindsamismatchquicklyandmoveontothenextpositionwithoutgoingthroughallmsteps.ButthismethodstillcantakeO(mn)forsomeinputs.Inonebadexample,allcharactersinT[]are"a"s

5、,andP[]isall"a"'sexceptforone"b"attheend.Thenittakesmcomparisonseachtimetodiscoverthatyoudon'thaveamatch,somnoverall.Here'samoretypicalexample.Eachrowrepresentsaniterationoftheouterloop,witheachcharacterintherowrepresentingtheresultofacomparison(Xifthecomparisonwasunequal).Su

6、pposewe'relookingforpattern"nano"intext"banananobano".01234567891011T:banananobanoi=0:Xi=1:Xi=2:nanXi=3:Xi=4:nanoi=5:Xi=6:nXi=7:Xi=8:Xi=9:nXi=10:XSomeofthesecomparisonsarewastedwork!Forinstance,afteriterationi=2,weknowfromthecomparisonswe'vedonethatT[3]="a",sothereisnopointco

7、mparingitto"n"initerationi=3.AndwealsoknowthatT[4]="n",sothereisnopointmakingthesamecomparisoniniterationi=4.SkippingouteriterationsTheKnuth-Morris-Prattideais,inthissortofsituation,afteryou'veinvestedalotofworkmakingcomparisonsintheinnerloopofthecode,youknowalotaboutwhat'sin

8、thetext.Specifically,ifyou'vefoundapartialmatchofjcharactersstarting