模式匹配与KMP算法

单击此处编辑标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2006-4-9,*,模式匹配与,KMP,算法,Zn,OUTLINE,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,OUTLINE,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,哪个是今天要讨论的模式匹配,the,The,quick brown fox jumps over the lazy dog,jay,The quick brown fox,j,umps over the l,a,z,y,dog,模式匹配,Finding all occurrences of a pattern in a text,eg. abc in acbcdabc,OUTLINE,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,The naive string-matching algorithm,ababcabcacbab,abcac,How does it work?,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,第一次匹配,第二次匹配,第三次匹配,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,第六次匹配,第五次匹配,第四次匹配,int Normal(int pos),int i,j;,i=pos;j=0;,while(si!=0&jlength),if(si=tj)i+;j+;,elsei=i-j+1;j=0;,if(j=length),return i-length;,else,return -1;,复杂度分析,一般情况,效率可以近似认为,O(m+n),极端特殊情况,O(mn),OUTLINE,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,Whats KMP?,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,岁！后来，此书与牛顿的“自然哲学的数学原理”等一起，被评为“世界历史上最伟大的十种科学著作”之一。,The KMP string-matching algorithm,abbcaccabbaabcababcdbac,abcd,How does it work?,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,第三次匹配,第二次匹配,第一次匹配,Nextj,j,0 1 2 3 4,模式串,a b c a c,Nextj,-1 0 0 0 1,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,int KMP(char*t,int pos),int i,j;,i=pos;,j=0;,while(si!=0&jlength),if(j=-1|tj=si)i+;j+;,elsej=nextj;,if(j=length),return i-j;,else,return -1;,复杂度分析,O(m+n),How to gain nextj?,以眼杀人观察法,a b a a b c a c,-1,1,1,2,0,0,0,1,a,b,a,a,a,b,c,c,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,程序实现,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,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;,OUTLINE,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,朴素算法与,KMP,算法的比较,复杂度,使用资源,效率,KMP,算法的改进,一个例子,模式串,:aaaab,主串,: aaabaaaab,j,0 1 2 3 4,模式,a,a a a b,N,extj,-1 0 1 2 3,N,extvalj,-1-1 -1 -1 3,OUTLINE,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,更多模式匹配算法,Boyer-Moore,算法,这个算法,KMP,算法的不同点是在作,sk+1.k+m,与,t1.m,的匹配测试时是从右到左，而不是从左到右。,Rabin-Karp,算法,这个算法用到数论中诸如两个整数关于第三个整数取模的等价性等初等概念。,SUMMARY,什么是模式匹配,朴素匹配算法,KMP,算法,效率对比,更多模式匹配算法,THANK YOU!,Zn,