課件kmp算法介紹KMP

1、by Chapter1:KMP算首先看一下 KMPProcedureKMP(p,t:k:= prefix1 := Fori:=2TomDok := prefixk;Ifpk+1=piThenInc(k); prefixi := k;q := 0;Fori:=1TonDoWhile(q0)And(pq+1ti)Do q := prefixq;q := q + 1;Ifq=mThenBegin O(mOKMP abacabbcacab這時候先將模式串進(jìn)行自身匹配，即 prefix3=1。當(dāng)查找abacabbcacab這時先比對主串的第一個位置，相同，這時 q=1，i=1abacabbcacab再比

2、對第二個位置，不同，此時 q=0，i=2abacabbcacab繼續(xù)對比第三個位置，這次比較不進(jìn)入語句，進(jìn)入語句，此時 q=1，i=3abacabbcacab接下來是第四個位置，對比結(jié)束后 q=2，i=4abacabbcacab然后是第五個位置，q=3，i=5abacabbcacababacabbcacabChapter 2:KMP 算法和樸素的匹配算法對從上面的分析，可以看出 KMP 算比普通算法快很多。但是有的同學(xué)不放心，問道：會不會出現(xiàn) KMP 算法比普通算法慢的情況呢？讓來做個測試吧。測試機(jī)器的配置是Core Duo T2050，1GB 內(nèi)存，80GB PATA 硬盤GeForce G

3、o 7300 顯卡。為了 comp-0(comp1.in):用時 = 0.02s:空間 = 57.83M comp-1(comp2.in):用時 = 0.02s:空間 = 57.83M comp-2(comp3.in):用時 = 0.03s:空間 = 57.83M comp-3(comp4.in):用時 = 0.03s:空間 = 57.83M comp-4(comp5.in):用時 = 0.05s:空間 = 57.83M comp-5(comp6.in):用時 = 0.06s:空間 = 57.83M comp-6(comp7.in):用時 = 0.06s:空間 = 57.83M comp-7(

4、comp8.in):用時 = 0.36s:空間 = 57.83M comp-8(comp9.in):用時 = 0.41s:空間 = 57.83M comp-9(comp10.in) 0.02s:空 57.83Mcomp-0(comp1.in):用時 = 0.02s:空間 = 19.61M comp-1(comp2.in):用時 = 0.02s:空間 = 19.61M comp-2(comp3.in):用時 = 0.02s:空間 = 19.61M comp-3(comp4.in):用時 = 0.02s:空間 = 19.61M comp-4(comp5.in):用時 = 0.06s:空間 = 19

5、.61M comp-5(comp6.in):用時 = 0.06s:空間 = 19.61M comp-6(comp7.in):用時 = 0.06s:空間 = 19.61M comp-7(comp8.in):用時 = 0.47s:空間 = 19.61M comp-8(comp9.in):用時 = TLE:空間 = 19.61M comp-9(comp10.in) 0.28s:空 19.61M其中 comp-0 到 comp-7 是隨機(jī)生成的測試數(shù)據(jù)，主串最長 10000000，模式串最長 1000000.可發(fā)現(xiàn)在這些數(shù)據(jù)中，KMP 的優(yōu)勢并不明顯，甚至?xí)葮闼氐乃惴?。這是因?yàn)?KMP 使用了自身匹配的思是模式串為一長串 a 加一b，而主串是一串 a。其中 comp-8 主串長度為 10000000，模式串 100000，而 comp-9 主串長 100000，模式串 1000。可以明顯發(fā)現(xiàn) KMP 的速度優(yōu)勢 大，特 是 comp-8，KMPChapter 3:學(xué)習(xí) KMP可能有的同學(xué)會說：Pascal 中提供了一個 Pos 函數(shù)，它就是 KMP 算法寫出來的，為什么要學(xué)習(xí) 呢學(xué)會 KMP 算法就顯得很必要了。但這不是最主要的