kmp算法詳解

1、KMP字符串模式匹配詳解字符串模式匹配詳解KMP字符串模式匹配通俗點(diǎn)說(shuō)就是一種在一個(gè)字符串中定位另一個(gè)串的高效算法。簡(jiǎn)單匹配算法的時(shí)間復(fù)雜度為O(mn)KMP匹配算法?？梢宰C明它的時(shí)間復(fù)雜度為O(mn).。一.簡(jiǎn)單匹配算法簡(jiǎn)單匹配算法先來(lái)看一個(gè)簡(jiǎn)單匹配算法的函數(shù)：intIndex_BF(S[]T[]intpos)若串S中從第pos(S的下標(biāo)0≤posStrLength(S))個(gè)字符起存在和串T相同的子串，則稱匹配成功，返回第一個(gè)這樣的子

2、串在串S中的下標(biāo)，否則返回1inti=posj=0while(S[ij]!=0繼續(xù)比較后一字符elseij=0重新開始新的一輪匹配if(T[j]==0)returni匹配成功返回下標(biāo)elsereturn1串S中(第pos個(gè)字符起)不存在和串T相同的子串Index_BF此算法的思想是直截了當(dāng)?shù)模簩⒅鞔甋中某個(gè)位置i起始的子串和模式串T相比較。即從j=0起比較S[ij]與T[j]，若相等，則在主串S中存在以i為起始位置匹配成功的可能性，繼續(xù)

3、往后比較(j逐步增1)，直至與T串中最后一個(gè)字符相等為止，否則改從S串的下一個(gè)字符起重新開始進(jìn)行下一輪的“匹配“，即將串T向后滑動(dòng)一位，即i增1，而j退回至0，重新開始新一輪的匹配。二.KMP匹配算法匹配算法還是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，當(dāng)?shù)谝淮嗡阉鞯絊[5]和T[5]不等后，S下標(biāo)不是回溯到1，T下標(biāo)也不是回溯到開始，而是根據(jù)T中T[5]==’d’的模式函數(shù)值（

4、next[5]=2，為什么？后面講），直接比較S[5]和T[2]是否相等，因?yàn)橄嗟?，S和T的下標(biāo)同時(shí)增加因?yàn)橛窒嗟龋琒和T的下標(biāo)又同時(shí)增加。。。最終在S中找到了T。如圖：KMP匹配算法和簡(jiǎn)單匹配算法效率比較，一個(gè)極端的例子是：在S=“AAAAAA…AAB“(100個(gè)A)中查找T=”AAAAAAAAAB”簡(jiǎn)單匹配算法每次都是比較到T的結(jié)尾，發(fā)現(xiàn)字符不同，然后T的下標(biāo)回溯到開始，S的下標(biāo)也要回溯相同長(zhǎng)度后增1，繼續(xù)比較。如果使用KMP匹配算