?一、串的模式匹配

? ? ? ? 模式匹配問題：有兩個字符串T和P，稱串T為目標(biāo)(Target)，P為模式(Pattern)，要在串T中查找是否有與串P相等的字串。

二、BF模式匹配

具體算法如下：

? ? ? ? BF模式匹配簡單來說，就是將P[0]與T串逐字符比較，每次比較都從P串首個字符一直比較至最后一個字符，若遇到不匹配的字符則失敗，移動P[0]與串T下一個字符比較，重復(fù)上述過程。

三、KMP模式匹配算法

（一）基本思想? ? ? ??

? ? ? ? KMP算法是無回退的算法，這里的回退針對T串而言，具體指若用變量i掃描T串，在BF算法中，每次比對失敗而進行下一次比對時，i都會向前回退一些字符。而在KMP算法中，i將從T[0]一直掃描至T[n-1]，不會向前回退。下述情況中仍用變量i掃描T串，算法主要思想如下。

? ? ? ? 按照上述BF算法，若在第s趟掃描中失敗，在P[j]位匹配失敗，此時P[0]-P[j-1]與T[s]-T[s+j-1]完全一致，變量i指向T串s+j位置，第s+1趟掃描需要將P[0]右移一位，從T[s+1]開始比較。這里我們集中觀察失配的P[j]之前的情況。此時，注意第s+1趟的P[0]-P[j-2]和第s趟的P[1]-P[j-1]，現(xiàn)在這兩段子串相對應(yīng)，若P[0]-P[j-2]與P[1]-P[j-1]不完全逐位一致，則P[0]-P[j-2]與T[s+1]-T[s+j-1]無法匹配，因此第s+1趟必然匹配失敗。按照BF算法再右移，進行第s+2趟掃描，此時若P[0]-P[j-3]與P[2]-P[j-1]不完全逐位一致，則第s+2趟也必然匹配失敗。

? ? ? ? 當(dāng)P串逐位右移，虛線框內(nèi)的子串都不能與第s趟中虛線框內(nèi)的子串完全一致，直至第t趟，P[0]-P[k]與失配的P[j]前緊挨著的子串P[j-k-1]-P[j-1]完全一致時，接下來從P[k+1]開始與第s趟中失配的位置T[s+j]繼續(xù)比較。那么有沒有一種方法可以在第s趟匹配失敗之后，直接讓P串右移一大段距離，直接移動到第t趟的位置呢？這里我們可以觀察，P[0]-P[k]是串P的前綴子串，P[j-k-1]-P[j-1]是P[j]之前的串的后綴子串。也即當(dāng)P[j]位匹配失敗時，從P[0]-P[j-1]子串中，找處最大的相匹配的前綴子串和后綴子串，然后將串P直接右移使得兩個子串相對應(yīng)。

? ? ? ? 設(shè)找到的前綴子串為P[0]-P[k]，則當(dāng)s趟匹配失敗，此時我們可以令掃描串T的變量i不動，仍指向第s趟中失敗的的s+j位置，令掃描P串的變量指向k+1位置，直接從T[i]與P[k+1]開始向后比對，而P[0]-P[k]由于與第s趟中的后綴子串完全相同，不用再次掃描比對。

? ? ? ? 因此，現(xiàn)在問題就轉(zhuǎn)化為當(dāng)某一趟P[j]匹配失敗，如何確定k。這里引入next數(shù)組，next[j]的值代表當(dāng)P[j]與T[i]匹配失敗，下一次比較應(yīng)該從P[next[j]]和T[i]開始進行比較。很明顯，當(dāng)j=0，即串P首位都未匹配成功，此時令next[j]=-1，即需要i++，串P仍然從j=0位置開始比對。這里先給出求得next數(shù)組之后，進行KMP匹配過程的算法。

? ? ? ? 代碼中i和j分別為掃描串T和串P的變量。當(dāng)掃描完串T都未找到完全匹配的子串，跳出while循環(huán)，此時j<P.num（串P長度），返回-1。當(dāng)掃描到串P匹配子串，j==P.num跳出while循環(huán)，此時返回i-P.num，也即串P在串T中起始位置。

? ? ? ? 這里給出串P“abaabcac”的next數(shù)組，并給出其與一個串T匹配的過程。

（二）next數(shù)組的確定

? ? ? ? next數(shù)組定義如下。next[j]的值代表當(dāng)P[j]與T[i]匹配失敗，下一次比較應(yīng)該從P[next[j]]和T[i]開始進行比較。（也代表了P[0]-P[j-1]中找到最大的相匹配的前綴子串和后綴子串的長度）

? ? ? ? 當(dāng)j==0，串P首位都未匹配成功，此時令next[j]=-1，即需要i++，串P仍然從j=0位置開始比對。當(dāng)能從P[0]-P[j-1]中找到最大的相匹配的前綴子串和后綴子串，且前綴子串為P[0]-P[k]時，直接從k的下一位置k+1處開始繼續(xù)比對。這里要求0<=k<j-1，因為若k==j-1，則前后綴子串均為P[0]-P[j-1]，k+1仍為j，而此時我們已經(jīng)知道P[j]匹配失敗，因此k必然<j-1。對于其他情況，也即無法在P[0]-P[j-1]找到相匹配的前綴子串和后綴子串時，下一次令P[0]與T[i]比對，即next[j]=0。

? ? ? ? 那么當(dāng)某一趟P[j]匹配失敗，如何確定k呢。假設(shè)現(xiàn)在要求next[j]，那么我們先觀察next[j-1]。令a=next[j-1]，即對于P[0]-P[j-2]之中，有長度為a的最大的相匹配的前綴子串和后綴子串，即下圖藍色區(qū)域，當(dāng)P[j-1]匹配失敗，下一次直接從P[a]和T[i]開始比較，如下圖所示。

? ? ? ??現(xiàn)在，若兩塊藍色區(qū)域右側(cè)的字符相同，即若P[a]==P[j-1]，則在P[j]之前的串P[0]-P[j-1]之中，有長度為a+1的最大的相匹配的前綴子串和后綴子串，則next[j]=a+1=next[j-1]+1。若P[a]！=P[j-1]，此時我們希望在兩塊藍色區(qū)域內(nèi)，分別在左側(cè)藍色區(qū)域的左側(cè)和右側(cè)藍色區(qū)域的右側(cè)找到完全匹配的子串，然后再次進行兩個子串右側(cè)下一符號的比對。

? ? ? ??如上圖所示，假設(shè)我們在長度為a的藍色區(qū)域中找到兩塊最大的橙色區(qū)域相匹配，其長度為b，那么接下來我們只需要比較P[b]和P[j-1]，若其相等，則在P[j]之前的串P[0]-P[j-1]之中，有長度為b+1的最大的相匹配的前綴子串和后綴子串，則next[j]=b+1，若其不等，則繼續(xù)在橙色區(qū)域內(nèi)搜索。以此類推。此時我們發(fā)現(xiàn)，由于兩塊橙色區(qū)域處于兩塊藍色區(qū)域中，而兩塊藍色區(qū)域完全相同，因此右側(cè)橙色區(qū)域和左側(cè)藍色區(qū)域內(nèi)部右側(cè)長度為b的區(qū)域重合，因此找到最大的兩個橙色區(qū)域，也就變成了在左側(cè)長度為a的藍色區(qū)域內(nèi)，找到最大的相匹配的前綴子串和后綴子串，而這一最大長度也即next[a]。因此，在上一步我們發(fā)現(xiàn)P[a]！=P[j-1]之后，可以直接進行P[next[a]]（在這里也即P[b]）與P[j-1]的判斷，若二者相等，則next[j]=next[a]+1（b+1），若不等，則繼續(xù)進行P[next[next[a]]]與P[j-1]的判斷，以此類推。

? ? ? ? 下面給出計算next數(shù)組的代碼。

? ? ? ? ?代碼中首先令next[0]=-1，for循環(huán)進行P.num-1次，依次給next[1]，next[2]...賦值。在計算next[j]時，在while循環(huán)中，當(dāng)P[k]==P[j-1]，也即找到P[0]-P[j-2]中相匹配的長度為k的前綴子串和后綴子串，且此時兩個子串的下一位也相同（P[k]==P[j-1]），則跳出while循環(huán)，next[j]=k+1。若未找到相匹配的前綴子串和后綴子串，其滿足前綴子串的下一位與P[j-1]相同，則最終k==-1，跳出while循環(huán)，令next[j]=0，下一次串P從頭開始比較。