课件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这时候先将模式串进行自身匹配，即 prefix3=1。当查找abacabbcacab这时先比对主串的第一个位置，相同，这时 q=1，i=1abacabbcacab再比

2、对第二个位置，不同，此时 q=0，i=2abacabbcacab继续对比第三个位置，这次比较不进入语句，进入语句，此时 q=1，i=3abacabbcacab接下来是第四个位置，对比结束后 q=2，i=4abacabbcacab然后是第五个位置，q=3，i=5abacabbcacababacabbcacabChapter 2:KMP 算法和朴素的匹配算法对从上面的分析，可以看出 KMP 算比普通算法快很多。但是有的同学不放心，问道：会不会出现 KMP 算法比普通算法慢的情况呢？让来做个测试吧。测试机器的配置是Core Duo T2050，1GB 内存，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 是随机生成的测试数据，主串最长 10000000，模式串最长 1000000.可发现在这些数据中，KMP 的优势并不明显，甚至会比朴素的算法慢。这是因为 KMP 使用了自身匹配的思是模式串为一长串 a 加一b，而主串是一串 a。其中 comp-8 主串长度为 10000000，模式串 100000，而 comp-9 主串长 100000，模式串 1000。可以明显发现 KMP 的速度优势 大，特 是 comp-8，KMPChapter 3:学习 KMP可能有的同学会说：Pascal 中提供了一个 Pos 函数，它就是 KMP 算法写出来的，为什么要学习 呢学会 KMP 算法就显得很必要了。但这不是最主要的