模式匹與KMP算法

1、2006-4-91/41模式匹配與kmp算法zn http:/ quick brown fox jumps over the lazy dogljaylthe quick brown fox jumps over the lazy dog2006-4-95/41模式匹配lfinding all occurrences of a pattern in a text leg. abc in acbcdabc 2006-4-96/41outlinel什么是模式匹配l樸素匹配算法lkmp算法l效率對比l更多模式匹配算法2006-4-97/41the naive string-matching algo

2、rithm lababcabcacbablabcaclhow does it work?2006-4-98/41a 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/41a 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第六次匹配第五次匹配第四次

3、匹配2006-4-910/41int 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;elsereturn -1;2006-4-911/41復(fù)雜度分析l一般情況效率可以近似認(rèn)為o(m+n)l極端特殊情況o(mn)2006-4-912/41outlinel什么是模式匹配l樸素匹配算法lkmp算法l效率對比l更多模式匹配算法2006-4-913/41whats kmp?2006-4-914/41knuth-morri

4、s-prattprofessor emeritus of the art of computer programming at stanford university, welcomes you to his home page. donald e. knuth，1938年出生于wisconsin。1960年，當(dāng)他畢業(yè)于case institute of technology數(shù)學(xué)系時(shí)，因?yàn)槌煽冞^于出色，被校方打破歷史慣例，同時(shí)授予學(xué)士和碩士學(xué)位。他隨即進(jìn)入大名鼎鼎的加州理工學(xué)院數(shù)學(xué)系，僅用三年時(shí)間便取得博士學(xué)位，此時(shí)年僅25歲。 畢業(yè)后留校任助理教授，28歲時(shí)升為副教授。30歲時(shí)，加盟斯坦福大

5、學(xué)計(jì)算機(jī)系，任正教授。從31歲那年起，他開始出版他的歷史性經(jīng)典巨著：the art of computer programming。他計(jì)劃共寫7卷，然而僅僅出版三卷之后，已經(jīng)震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)turing award!此時(shí)，他年僅38歲！后來，此書與牛頓的“自然哲學(xué)的數(shù)學(xué)原理”等一起，被評為“世界歷史上最偉大的十種科學(xué)著作”之一。2006-4-915/41the kmp string-matching algorithm labbcaccabbaabcababcdbaclabcdlhow does it work?2006-4-916/41a b a b c a b c

6、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-917/41nextjj 0 1 2 3 4模式串 a b c a cnextj-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-918/41int kmp(char*t,int pos)int i,j;i=pos;j=0;while(si!=0&jlength)if(j=-1|tj=s

7、i)i+;j+;elsej=nextj;if(j=length)return i-j;elsereturn -1;2006-4-919/41復(fù)雜度分析o(m+n)2006-4-920/41how to gain nextj?2006-4-921/41以眼殺人觀察法a b a a b c a c-111 2000 1a baaab cc2006-4-922/41exercisela b c a b a a b c b cla a b a a c a a d ala 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

8、1 2 02006-4-923/41程序?qū)崿F(xiàn)a b a a b c a cnexti -111 2000 1tif(j=-1|sj=ti)i+;j+;nexti=j;elsej=nextjsji2006-4-924/41void 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-925/41outlinel什么是模式匹配l樸素匹配算法lkmp算法l效率對比l更多模式匹配算法2006-4-926/41樸素算法與kmp算法的比較l復(fù)雜度l使用資源l效率2006-4-927/41kmp算法的改進(jìn)l一個例子模式串:aaaab主串: aaabaaaabj0 1 2 3 4模式a a a a bnextj-1 0 1 2 3nextvalj-1-1 -1 -1 32006-4-928/41outlinel什么是模式匹配l樸素匹配算法lkmp算法l效率對比l更多模式匹配算法2006-4-929/41更多模式匹配算法lboyer-moore算法 這個算法kmp算法的不同點(diǎn)是在作sk+1.k+m與t1.m的匹配測試時(shí)是從右到左，而不是從