KMP算法

2006-4-91/41模式匹配与KMP算法Zn什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-93/41OUTLINE什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-94/41哪个是今天要讨论的模式匹配theThequickbrownfoxjumpsoverthelazydogjayThequickbrownfoxjumpsoverthelazydog2006-4-95/41模式匹配Findingalloccurrencesofapatterninatexteg.'abc'in'acbcdabc'2006-4-96/41OUTLINE什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-97/41Thenaivestring-matchingalgorithmababcabcacbababcacHowdoesitwork?2006-4-98/41ababcabcacbabababcabcacbabababcabcacbababcacabcacabcac第一次匹配第二次匹配第三次匹配2006-4-99/41ababcabcacbabababcabcacbabababcabcacbababcacabcacabcac第六次匹配第五次匹配第四次匹配2006-4-910/41intNormal(intpos){inti,j;i=pos;j=0;while(s[i]!=0&&jlength){if(s[i]==t[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j==length)returni-length;elsereturn-1;}2006-4-911/41复杂度分析一般情况效率可以近似认为O(m+n)极端特殊情况O(mn)2006-4-912/41OUTLINE什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-913/41What’sKMP?2006-4-914/41Knuth-Morris-PrattProfessorEmeritusofTheArtofComputerProgrammingatStanfordUniversity,welcomesyoutohishomepage.DonaldE.Knuth，1938年出生于Wisconsin。1960年，当他毕业于CaseInstituteofTechnology数学系时，因为成绩过于出色，被校方打破历史惯例，同时授予学士和硕士学位。他随即进入大名鼎鼎的加州理工学院数学系，仅用三年时间便取得博士学位，此时年仅25岁。毕业后留校任助理教授，28岁时升为副教授。30岁时，加盟斯坦福大学计算机系，任正教授。从31岁那年起，他开始出版他的历史性经典巨著：TheArtofComputerProgramming。他计划共写7卷，然而仅仅出版三卷之后，已经震惊世界，使他获得计算机科学界的最高荣誉TuringAward!此时，他年仅38岁！后来，此书与牛顿的“自然哲学的数学原理”等一起，被评为“世界历史上最伟大的十种科学著作”之一。2006-4-915/41TheKMPstring-matchingalgorithmabbcaccabbaabcababcdbacabcdHowdoesitwork?2006-4-916/41ababcabcacbabababcabcacbabababcabcacbababcacabcacabcac第三次匹配第二次匹配第一次匹配2006-4-917/41Next[j]j01234模式串abcacNext[j]-10001ababcabcacbababcacabcacabcac2006-4-918/41intKMP(char*t,intpos){inti,j;i=pos;j=0;while(s[i]!=0&&jlength){if(j==-1||t[j]==s[i]){i++;j++;}else{j=next[j];}}if(j==length)returni-j;elsereturn-1;}2006-4-919/41复杂度分析O(m+n)2006-4-920/41Howtogainnext[j]?2006-4-921/41以眼杀人－－观察法abaabcac-11120001abaaabcc2006-4-922/41Exerciseabcabaabcbcaabaacaadaabababab-10001211200-10012345-10101201202006-4-923/41程序实现abaabcacNext[i]-11120001TIf(j==-1||s[j]==t[i])i++;j++;next[i]=j;Elsej=next[j]Sji2006-4-924/41voidCalcNext(char*t){inti,j;i=0;next[0]=-1;j=-1;while(ilength-1){if(j==-1||t[i]==t[j]){i++;j++;next[i]=j;}else{j=next[j];}}}2006-4-925/41OUTLINE什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-926/41朴素算法与KMP算法的比较复杂度使用资源效率2006-4-927/41KMP算法的改进一个例子模式串:aaaab主串:aaabaaaabj01234模式aaaabNext[j]-10123Nextval[j]-1-1-1-132006-4-928/41OUTLINE什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-929/41更多模式匹配算法Boyer-Moore算法这个算法KMP算法的不同点是在作s[k+1..k+m]与t[1..m]的匹配测试时是从右到左，而不是从左到右。Rabin-Karp算法这个算法用到数论中诸如两个整数关于第三个整数取模的等价性等初等概念。2006-4-930/41SUMMARY什么是模式匹配朴素匹配算法KMP算法效率对比更多模式匹配算法2006-4-931/41THANKYOU!Zn