《模式匹配与KMP算法.ppt》由会员分享，可在线阅读，更多相关《模式匹配与KMP算法.ppt（31页珍藏版）》请在三一文库上搜索。
1、2006-4-9,1/41,模式匹配与KMP算法,Zn http:/ 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,3/41,OUTLINE,什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,4/41,哪个是今天要讨论的模式匹配,the The quick brown fox jumps over the lazy dog jay The quick brown fox jumps over the lazy dog,2006-4-9,5/41,模式匹配,Finding all occurrences of a pattern i
2、n a text eg. abc in acbcdabc,2006-4-9,6/41,OUTLINE,什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,7/41,The naive string-matching algorithm,ababcabcacbab abcac How does it work?,2006-4-9,8/41,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b c a c,a b c a c,a b c a c,第一次匹
3、配,第二次匹配,第三次匹配,2006-4-9,9/41,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b c a c,a b c a c,a b c a c,第六次匹配,第五次匹配,第四次匹配,2006-4-9,10/41,int Normal(int pos) int i,j; i=pos;j=0; while(si!=0 ,2006-4-9,11/41,复杂度分析,一般情况 效率可以近似认为O(m+n) 极端特殊情况 O(mn),2006-4-9,12/41,OUTLINE,什
4、么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,13/41,Whats KMP?,2006-4-9,14/41,Knuth-Morris-Pratt,Professor Emeritus of The Art of Computer Programming at Stanford University, welcomes you to his home page.,Donald E. Knuth，1938年出生于Wisconsin。1960年，当他毕业于Case Institute of Technology数学系时，因为成绩过于出色，被校方打破历史惯例，
5、同时授予学士和硕士学位。他随即进入大名鼎鼎的加州理工学院数学系，仅用三年时间便取得博士学位，此时年仅25岁。 毕业后留校任助理教授，28岁时升为副教授。30岁时，加盟斯坦福大学计算机系，任正教授。从31岁那年起，他开始出版他的历史性经典巨著：The Art of Computer Programming。他计划共写7卷，然而仅仅出版三卷之后，已经震惊世界，使他获得计算机科学界的最高荣誉Turing Award!此时，他年仅38岁！后来，此书与牛顿的“自然哲学的数学原理”等一起，被评为“世界历史上最伟大的十种科学著作”之一。,2006-4-9,15/41,The KMP string-match
6、ing algorithm,abbcaccabbaabcababcdbac abcd How does it work?,2006-4-9,16/41,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b a b c a b c a c b a b,a b c a c,a b c a c,a b c a c,第三次匹配,第二次匹配,第一次匹配,2006-4-9,17/41,Nextj,a b a b c a b c a c b a b,a b c a c,a b c a c,a b c a c,2006-4-9,18/41,int KM
7、P(char*t,int pos) int i,j; i=pos; j=0; while(si!=0 ,2006-4-9,19/41,复杂度分析,O(m+n),2006-4-9,20/41,How to gain nextj?,2006-4-9,21/41,以眼杀人观察法,a b a a b c a c,-1,1,1,2,0,0,0,1,a,b,a,a,a,b,c,c,2006-4-9,22/41,Exercise,a b c a b a a b c b c,a a b a a c a a d a,a b a b a b a b,-1 0 0 0 1 2 1 1 2 0 0,-1 0 0 1
8、2 3 4 5,-1 0 1 0 1 2 0 1 2 0,2006-4-9,23/41,程序实现,a b a a b c a c,Nexti,-1,1,1,2,0,0,0,1,T,If(j=-1|sj=ti) i+;j+;nexti=j;,Else j=nextj,S,j,i,2006-4-9,24/41,void CalcNext(char*t) int i,j; i=0; next0=-1; j=-1; while(ilength-1) if(j=-1|ti=tj)i+;j+;nexti=j; elsej=nextj; ,2006-4-9,25/41,OUTLINE,什么是模式匹配 朴素匹
9、配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,26/41,朴素算法与KMP算法的比较,复杂度 使用资源 效率,2006-4-9,27/41,KMP算法的改进,一个例子 模式串:aaaab 主串: aaabaaaab,2006-4-9,28/41,OUTLINE,什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,29/41,更多模式匹配算法,Boyer-Moore算法 这个算法KMP算法的不同点是在作sk+1k+m与t1m的匹配测试时是从右到左，而不是从左到右。 Rabin-Karp算法 这个算法用到数论中诸如两个整数关于第三个整数取模的等价性等初等概念。,2006-4-9,30/41,SUMMARY,什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法,2006-4-9,31/41,THANK YOU!,Zn http:/