模式匹配与KMP算法.ppt
2006-4-9,1/41,模式匹配与KMP算法,Zn http:/,2006-4-9,2/41,OUTLINE,什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法,2006-4-9,3/41,OUTLINE,什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法,2006-4-9,4/41,哪个是今天要讨论的模式匹配,theThe quick brown fox jumps over the lazy dogjayThe quick brown fox jumps over the lazy dog,2006-4-9,5/41,模式匹配,Finding all occurrences of a pattern in a text eg.abc in acbcdabc,2006-4-9,6/41,OUTLINE,什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法,2006-4-9,7/41,The naive string-matching algorithm,ababcabcacbababcacHow 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,第一次匹配,第二次匹配,第三次匹配,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,什么是模式匹配朴素匹配算法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数学系时，因为成绩过于出色，被校方打破历史惯例，同时授予学士和硕士学位。他随即进入大名鼎鼎的加州理工学院数学系，仅用三年时间便取得博士学位，此时年仅25岁。毕业后留校任助理教授，28岁时升为副教授。30岁时，加盟斯坦福大学计算机系，任正教授。从31岁那年起，他开始出版他的历史性经典巨著：The Art of Computer Programming。他计划共写7卷，然而仅仅出版三卷之后，已经震惊世界，使他获得计算机科学界的最高荣誉Turing Award!此时，他年仅38岁！后来，此书与牛顿的“自然哲学的数学原理”等一起，被评为“世界历史上最伟大的十种科学著作”之一。,2006-4-9,15/41,The KMP string-matching algorithm,abbcaccabbaabcababcdbacabcdHow 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 KMP(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 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;,Elsej=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,什么是模式匹配朴素匹配算法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+1.k+m与t1.m的匹配测试时是从右到左，而不是从左到右。Rabin-Karp算法这个算法用到数论中诸如两个整数关于第三个整数取模的等价性等初等概念。,2006-4-9,30/41,SUMMARY,什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法,2006-4-9,31/41,THANK YOU!,Zn http:/,
