恐怕現(xiàn)在用過電腦的人，一定都知道大部分帶文本編輯功能的軟件都有一個(gè)快捷鍵ctrl+f 吧（比如word）。這個(gè)功能主要來完成“查找”，“替換”和“全部替換”功能的，其實(shí)這就是典型的模式匹配的應(yīng)用，即在文本文件中查找串。

1.模式匹配
模式匹配的模型大概是這樣的：給定兩個(gè)字符串變量S和P，其中S成為目標(biāo)串，其中包含n個(gè)字符，P稱為模式串，包含m個(gè)字符，其中m<=n。從S的給定位置（通常是S的第一個(gè)位置）開始搜索模式P。如果找到，則返回模式P在目標(biāo)串中的位置（即：P的第一個(gè)字符在S中的下標(biāo)）。如果在目標(biāo)串S中沒有找到模式串P，則返回-1.這就是模式匹配的定義啦，下面來看看怎么實(shí)現(xiàn)模式匹配算法吧。

2.樸素的模式匹配
樸素的模式匹配算法非常簡單，容易理解，大概思路是這樣的：從S的第一個(gè)字符S0開始，將P中的字符依次和S中字符比較，若S0=P0 && …… && Sm-1 = Pm-1，則證明匹配成功，剩下的匹配無需進(jìn)行了，返回下標(biāo)0。若在某一步Si != Pi 則P中剩下的字符也不用比較了，不可能匹配成功了，然后從S中第二個(gè)字符開始與P中第一個(gè)字符進(jìn)行比較，同理，也是知道Sm = Pm-1或者找到某個(gè)i使得Si != S-1為止。依次類推若知道以S中第n-m個(gè)開始字符為止，還沒有匹配成功則證明S中不存模式P。（想想為什么這里強(qiáng)調(diào)是n-m）這個(gè)代碼實(shí)現(xiàn)應(yīng)該是非常簡單的，具體開始參考strstr函數(shù)的內(nèi)部實(shí)現(xiàn)。可以看看百度百科，給個(gè)鏈接http://baike.baidu.com/view/745156.htm，這里不寫出來了，還得趕緊進(jìn)入正題KMP呢。

3.快速模式匹配算法（KMP）
樸素的模式匹配效率不高的主要原因是進(jìn)行了重復(fù)的字符比較。下一次比較和上一次比較沒有任何的聯(lián)系，是樸素模式匹配的缺點(diǎn)，其實(shí)上一次比較的比較結(jié)果是可以利用的，這就產(chǎn)生了快速模式匹配。在樸素的模式匹配中，目標(biāo)串S的下標(biāo)移動(dòng)是一步一步的，這其實(shí)并不好，移動(dòng)步數(shù)沒有必要為1。
現(xiàn)在不妨假設(shè)，當(dāng)前匹配情況是這樣的：S0 …… St St+1 …… St+j  與 P0 P1…… Pj ，現(xiàn)在正在嘗試匹配的字符是St+j+1和Pj+1，并且St+j+1 != Pj+1，言外之意就是說St St+1……St+j和P0 P1……Pj是完全匹配的。那么這個(gè)時(shí)候，S中下一次匹配開始位置應(yīng)該是什么呢？？按照樸素的模式匹配，下次比較應(yīng)該從St+1開始，并且令St+1和P0比較，但是在快速模式匹配中并不是這樣，快速模式匹配選擇St+j+1和Pk+1比較，K是什么呢？K是這樣的一個(gè)值，使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配，不妨設(shè)k=next[j]，因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要進(jìn)行匹配的兩個(gè)字符應(yīng)為St+j+1和Pk+1。S和P都沒有回溯到下標(biāo)0在進(jìn)行比較，這就是KMP之所以快的原因啦。
現(xiàn)在關(guān)鍵問題來了，這個(gè)K怎么能得到呢？如果得到這個(gè)K值復(fù)雜度高，那這個(gè)思路就不好了，其實(shí)這個(gè)K呢，只和模式串P有關(guān)系，并且要求m個(gè)k，k = next[j]，因此只要算一次存儲(chǔ)到next數(shù)組中就可以了，并且時(shí)間復(fù)雜度和m有關(guān)系（線性關(guān)系）?？纯淳唧w怎么求next數(shù)組的值，即求k。
用歸納法求next[]：設(shè)next(0) = -1，若已知next(j) = k，欲求得next[j+1]。
（1）如果Pk+1 = Pj+1，顯然next[j+1] = k+1.如果Pk+1 != Pj+1，則next[j+1] < next[j]，于是尋找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。也就是說h = next(k);看出來了吧，這是個(gè)迭代的過程。（也就是以前的結(jié)果對求以后的值有用）
（2）如果不存這樣的h，說明P0 P1……Pj+1中沒有前后相等的子串，因此next[j+1] =-1.
（3）如果存在這樣的h，繼續(xù)檢驗(yàn)Ph和Pj是否相等。知道找到這中相等的情況，或者確定為-1求next[j+1]的過程結(jié)束。
看看實(shí)現(xiàn)的代碼：

現(xiàn)在有了next數(shù)組保存的k值，就可以實(shí)現(xiàn)KMP算法了：

時(shí)間復(fù)雜度：
對于Next函數(shù)近似接近O（m），KMP算法的時(shí)間復(fù)雜度為O(n)，所以整個(gè)算法的時(shí)間復(fù)雜度為O(n+m)
空間復(fù)雜度：
多引入了O（m）的空間復(fù)雜度。
4.應(yīng)用KMP的一道面試題
給定兩個(gè)字符串是s1和s2，要判定s2是否能夠被s1做循環(huán)移位得到的字符串包含。例如s1=AABCD，s2 =CDAA，返回true，因?yàn)閟1循環(huán)移位可以變成CDAAB。給定s1=ACBD和s2=ACBD則返回false。
分析：不難發(fā)現(xiàn)對s2移位得到的字符串都將是字符串s1s1的子串，如果s2可以有s1循環(huán)移位得到，那么s2一定是s1s1的子串，這時(shí)KMP算法是不是就很管用了呢。

最新評論