模式匹配与KMP算法.ppt

2006-4-9,1/41,模式匹配与KMP算法,Zn /znzhou/,2006-4-9,2/41,OUTLINE,什么是模式匹配 朴素匹配算法 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 in 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,第一次匹配,第二次匹配,第三次匹配,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,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 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;,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,什么是模式匹配 朴素匹配算法 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算法 这个算法用到数论