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

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

3、往后比較(j逐步增1)，直至與T串中最后一個字符相等為止，否則改從S串的下一個字符起重新開始進行下一輪的“匹配“，即將串T向后滑動一位，即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]是否相等，因為相等，S和T的下標(biāo)同時增加因為又相等，S和T的下標(biāo)又同時增加。。。最終在S中找到了T。如圖：KMP匹配算法和簡單匹配算法效率比較，一個極端的例子是：在S=“AAAAAA…AAB“(100個A)中查找T=”AAAAAAAAAB”簡單匹配算法每次都是比較到T的結(jié)尾，發(fā)現(xiàn)字符不同，然后T的下標(biāo)回溯到開始，S的下標(biāo)也要回溯相同長度后增1，繼續(xù)比較。如果使用KMP匹配算