串比對問題與KMP算法
目錄
問題
蠻力算法
KMP算法-主算法
KMP算法-生成next表
KMP算法-複雜度分析
KMP算法-next表改進
問題
在現實中經常遇到這樣的需求：
給一個較長的串T，長n，和一個較短的串P，長m，設計算法判斷P中是否包含T，若有，傳回T中和P比對的子串起點的下标。
蠻力算法
最容易想到的就是兩個串頭部對齊，兩個指針i、j表示T和P中進行比對的元素的下标（初始化為0），逐個元素比對，遇到比對失敗（稱這種情況為失配）則将P右移一步（P的滑動是通過指針的回退實作的，i每次回退到對齊位置的下一格，j每次回到0），再重新開始比對，直到找到T中比對的子串（比對成功）或直到T頭部到n-m處的情況下（可能比對的最後位置）還出現失配（比對失敗），算法結束。代碼如下
public int bruteForce(char [] T, char [] P) {
int n = T.length, m = P.length;
int i = 0, j = 0;
while(i < m && j < n) {
if(T[i] == P[j]) {
i++; j++;
}else {
i -= j - 1;//每次回退j都回到0， 失配時走了j步
j = 0;
}
}
return i - j;//i-j就是對齊的位置
}
這種算法簡單粗暴，逐次比對，被稱為蠻力算法。表現與資料情況有關：字元集越小，局部比對的機率就越大，回退次數就越多，浪費掉的運算就越多。不難看出蠻力算法的時間複雜度是O(n*m)。有沒有更快的方法呢？
KMP算法-主算法
我們觀察一下蠻力算法比對的過程。每一次失配，都要把j回退到0重新比對，每一次都是新的開始。而前面雖然有局部比對的字首，但是資訊都被丢棄掉了，進行了大量的無效運算。如果能充分利用失配時局部比對的資訊，就能大幅加快比對的速度。比如圖中的情況
這種情況屬于“對于P的真字首P[0 , j)，存在長度為 t 的真字首P[0 , t)和真字尾P[j - t , j)完全比對，且 t 是滿足條件的最大長度”。同時，因為t時長度為j的子串P[0 , j)的真字首、真字尾的長度，是以t < j。
再看一下示意圖，參與比對的T[i - j, i)和P[0 , j)是完全相同的，在P向右逐漸滑動的過程中，任何時刻有兩種可能：P和T[i - j, i)對齊的部分完全比對 or 不完全比對。對于完全比對的情況，就可以跳過T[i - j, i)從T[i]開始進行比對；而不完全比對的情況則一定存在失配，需要繼續滑動，也就沒有研究的必要。是以，我們的目标就是跳過不完全比對的情況，進而加快比對速度。
而“對于P的真字首P[0 , j)，存在長度為 t 的真字首P[0 , t)和真字尾P[j - t , j)完全比對，且 t 是滿足條件的最大長度”就是解決問題的關鍵。在這種情況下，可以通過向右滑動P，把令P[0 , t)占據P[j - t , j)的位置，P[0 , t) == P[j - t , j)、P[j - t , j) == T[j - t , j)，此時P[0 , t)和T[j - t , j)必然是完全比對的，可以直接省略這一段，直接從剛剛失配的T[i]（即P[t]）開始繼續比對。代碼主體如下：
public int kmp(char [] T, char [] P) {
int n = T.length, m = P.length;
int i = 0, j = 0;
int [] next = makeNext(P);
while(j < m || i < n) {
if(j < 0 || T[i] == P[j]) {//j<0一定要寫在前面,具體意思暫時不用明白，下面會講
i++; j++;
}else {
j = next[j];
}
}
return i - j;
}
KMP算法-生成NEXT表
要實作“令P[0 , t)占據P[j - t , j)的位置”，那麼當任意P[j]失配時，必須知道現在P要滑動到什麼位置，也就是指針j要回退到什麼位置。方法是：建構一個next表，在裡面儲存在P的每個下标位置失配的時候，j要回退到的位置。
再次說明next表中元素的含義。對于任一 next[j] = t，表示“對于P的真字首P[0 , j)，存在長度為 t 的真字首P[0 , t)和真字尾P[j - t , j)完全比對，且 t 是滿足條件的最大長度”。 P[t]正是上述字首的下一個元素。
在對比時，有兩種可能：P[j] == P[next[j]] 、P[j] ！= P[next[j]]。
當P[j] == P[next[j]]，很自然地将t增加1，next[j + 1] = next[j] + 1。
當P[j] != P[next[j]]，要找到下一個盡可能長，可以對齊一部分P的比對位置。也就是說找到在目前的P[0 , j)上自比對的真字首和真字尾換過來。目标位置就是next[j]。如果再不行，就是next[next[j]]，以此類推，和主算法的思路是一樣的。事實上生成next表的過程就是P自身對子串進行比對的過程。t < j，故next[j]一定在 j 前面，是以可以用遞推法生成next表，。
public int[] makeNext(char[] P) {
int m = P.length;
int [] next = new int[m];
int j = 0, t = -1;
next[0] = t;
while(j < m - 1) {
if(t < 0 || P[t] == P[j]) {//如果比對成功
next[j] = t;
}else {
t = next[t];
}
}
return next;
}
解釋一下代碼。為什麼t的初始值為-1？這個算法假象地在P[0]的前面放置了一個可以和任何元素比對的通配符 * ，秩為-1，這裡用t < 0表示和通配符比對成功，(t < 0 || P[t] == P[j]) 就是所有比對成功的情況。有了這個通配符，就可以開始遞推next表下面的每一個t了，每一次比較在最壞情況下也會在-1位置和這個通配符比對成功。
KMP算法-複雜度分析
設定一個觀察值k = 2 * i - j。
對于主算法，k初值為0，單調遞增，每次疊代不管進入哪種分支，k都遞增1(i、j同時+=1 或 i不變j+=1)，是以k可以用來訓示疊代次數。i最大為 n-1， j最小為 -1。當算法結束，有 k <= 2(n - 1) - (-1)。時間複雜度O(n)。
生成next表的過程和主算法思路相似，不難得出時間複雜度O(m)。
是以整體的複雜度為O(n+m)，線性複雜度，比O(n*m)的蠻力算法快得多。
KMP算法-NEXT表改進
上面的算法已經很快了，但還有改進餘地。想象一下這種情況
public int[] makeBetterNext(char[] P) {
int m = P.length;
int [] next = new int[m];
int j = 0, t = -1;
next[0] = t;
while(j < m - 1) {
if(t < 0 || P[t] == P[j]) {
++j; ++t;
next[j] = P[j] != P[t]? t: next[t]; //next表相鄰兩元素一定不同，除非是兩個-1
}else {
t = next[t];
}
}
return next;
}