资源描述：
《算法分析与设计2005春.课件.第11讲 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、内容介绍•解决问题：模式匹配，对应实际问题：Lecture11模式匹配–文本文件字符串查找–格式文件中的字符串及其格式查找问题•算法：Naïve，RabinKarp,自动机，清华大学KMP，BM算法宋斌恒12Figure32.1Thestring-matchingproblem.Thegoalisto本章算法及其复杂度列表findalloccurrencesofthepatternP=abaainthetextT=abcabaabcabac.Thepatternoccursonlyonceinthetext,atshifts=
2、3.Theshifts=3issaidtobeavalidshift.EachcharacteroftheAlgorithmpreprocessingtimematchingtimepatternisconnectedbyaverticallinetothematchingcharacterinNaïve0O((n-m+1)m)thetext,andallmatchedcharactersareshowningreencolor.Rabin-KarpΘ(m)O((n-m+1)m)FiniteautomatonO(m
3、Σ
4、)Θ(
5、n)textTabcabaabcabacKnuthMorrisPrattO(m)Θ(n)BMpatternPabaa34TerminologyLemma32.1(Overlapping-suffixlemma)•Σ:字符集Supposethatx,y,andzarestringssuch•Σ*:由Σ生成的所有字符串，包括空串的thatx]zandy]z.If
6、x
7、≤
8、y
9、,thenx]y.集合,以下叙述x,y,z,w表示其元素If
10、x
11、≥
12、y
13、,theny]x.If
14、x
15、=
16、y
17、,thenx•Concatenationofx，
18、y：xy=y.•前缀：[:w[xÎthereexistsy，suchthatx=wy•后缀：]:w]xÎthereexistsy，suchthatx=yw561Figure32.3AgraphicalproofofLemma32.1.Wesupposethatx]aandy]z.Thethreepartsofthefigureillustratethethreecasesofthelemma.Verticallinesconnectmatchingregions(shownshaded)ofthestrings.(a)If
19、x
20、
21、≤
22、y
23、,thenx]y.(b)If
24、x
25、≥
26、y
27、,theny]x.(c)If
28、x
29、=
30、y
31、,thenx=y.NaïveStringmatchingalgorithm•Naïve-String-matcher(T,P)1.nÅlength[T]2.mÅlength[P]3.ForsÅ0ton-m1.IfP[1,…,m]==T[s+1,…,s+m]1.Print“Patternoccurswithshift”s78RabinKarpalgorithmKeyPointsofKarp-Rabin•HashValuepofastri
32、ngPwithmoduloq:•Howtocomputethevalueefficiently?–p=hash(P,m,q)=(P[m]
33、Σ
34、0+P[m-1]
35、Σ
36、1+P[m-2]
37、Σ
38、2+…+P[m-i]
39、Σ
40、i+…+P[1]
41、Σ
42、m-1)mod(q)–ts+1=Hash(T[s+1,m],m,q)–计算方法：多项式求值方法，–ts+1=(d(ts-T[s+1]h)+T[s+m+1])mod(q)•算法描述：–h=dm-1(modq)–给定字符串T和要找的子字符串P，–d是进位，如果是26个字符，则可以是26，–从i=1到L
43、ength[T]-Length[P]一般来讲取d为
44、Σ
45、•IfHash(P,m,q)!=Hash(T[i,m],m,q)continue•继续判断（naïve方法）•SpuriousHit•其中T[i,m]表示T从i开始长度为m的子串910235902314152673992123590231415267399217893110178451011791111122•Rabin-Karp-Matcher(T,P,d,q)1.n=length[T]2.m=length[P]3.h=dm-1(modq)4.p=03141521415
46、2≡(31415－3·10000)·10+2(mod13)5.T0=0≡(7－3·3)·10+2(mod13)6.Fori=1tom≡8(mod13)1.p=(dp+P[i])(modq)2.t0=(dt0+T[i])(modq)787.Fors=0ton-m1.Ifp=ts
