• 1. 模式匹配与KMP算法Zn http://spaces.msn.com/znzhou/2006-4-91/41
  • 2. OUTLINE什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-92
  • 3. OUTLINE什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-93
  • 4. 哪个是今天要讨论的模式匹配the The quick brown fox jumps over the lazy dog jay The quick brown fox jumps over the lazy dog 2006-4-94
  • 5. 模式匹配Finding all occurrences of a pattern in a text eg. 'abc' in 'acbcdabc' 2006-4-95
  • 6. OUTLINE什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-96
  • 7. The naive string-matching algorithm ababcabcacbab abcac How does it work?2006-4-97
  • 8. a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a c第一次匹配第二次匹配第三次匹配2006-4-98
  • 9. a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a c第六次匹配第五次匹配第四次匹配2006-4-99
  • 10. int Normal(int pos) { int i,j; i=pos;j=0; while(s[i]!=0&&j
  • 11. 复杂度分析一般情况 效率可以近似认为O(m+n) 极端特殊情况 O(mn)2006-4-911
  • 12. OUTLINE什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-912
  • 13. What’s KMP?2006-4-913
  • 14. Knuth-Morris-PrattProfessor 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-914
  • 15. The KMP string-matching algorithm abbcaccabbaabcababcdbac abcd How does it work?2006-4-915
  • 16. a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a c第三次匹配第二次匹配第一次匹配2006-4-916
  • 17. Next[j]j 0 1 2 3 4模式串 a b c a cNext[j]-1 0 0 0 1a b a b c a b c a c b a ba b c a ca b c a ca b c a c2006-4-917
  • 18. int KMP(char*t,int pos) { int i,j; i=pos; j=0; while(s[i]!=0&&j
  • 19. 复杂度分析O(m+n)2006-4-919
  • 20. How to gain next[j]?2006-4-920
  • 21. 以眼杀人--观察法a b a a b c a c-11120001abaaabcc2006-4-921
  • 22. Exercisea b c a b a a b c b ca a b a a c a a d aa 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 02006-4-922
  • 23. 程序实现a b a a b c a cNext[i]-11120001TIf(j==-1||s[j]==t[i]) i++;j++;next[i]=j;Else j=next[j]Sji2006-4-923
  • 24. void CalcNext(char*t) { int i,j; i=0; next[0]=-1; j=-1; while(i
  • 25. OUTLINE什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-925
  • 26. 朴素算法与KMP算法的比较复杂度 使用资源 效率2006-4-926
  • 27. KMP算法的改进一个例子 模式串:aaaab 主串: aaabaaaabj0 1 2 3 4模式a a a a bNext[j]-1 0 1 2 3Nextval[j]-1-1 -1 -1 32006-4-927
  • 28. OUTLINE什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-928
  • 29. 更多模式匹配算法Boyer-Moore算法 这个算法KMP算法的不同点是在作s[k+1..k+m]与t[1..m]的匹配测试时是从右到左,而不是从左到右。 Rabin-Karp算法 这个算法用到数论中诸如两个整数关于第三个整数取模的等价性等初等概念。 2006-4-929
  • 30. SUMMARY什么是模式匹配 朴素匹配算法 KMP算法 效率对比 更多模式匹配算法2006-4-930
  • 31. THANK YOU!Zn http://spaces.msn.com/znzhou/2006-4-931